Intution behind simple solution of this problem.

Revision en1, by nitin12384, 2021-08-26 08:41:44

The problem is "What is the number of recursive palindromic binary strings of length n ? " A string "s" of length n is recursively palindromic is "s" is a palindrome and the first half of "s", is also recursively palindrome. Example of recursively palindromic strings : 0001000 1011101 111

For example for n = 5, there are four such strings {00000, 00100, 11011, 11111}, so answer is 4.

What I came up with is : T1 = T2 = 2 (n is odd) Tn = 2*T((n-1)/2) (n is even) Tn = T(n/2)

Interestingly . It turns out that Tn = 2^(no. of set bits in binary representation of n) . Can someone explain an intuition behind this simple answer, and how can one come up with this solution ?

Reference :

Tags #string, #easy, #palindrome, #bit


  Rev. Lang. By When Δ Comment
en1 English nitin12384 2021-08-26 08:41:44 844 Initial revision (published)