### nitin12384's blog

By nitin12384, history, 3 years ago,

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 ?

• +1

 » 3 years ago, # | ← Rev. 2 →   0 Here, if n is even then you divide by 2 <=> right shift by 1.=> you divide n by 2 until an odd number appears. => if n becomes odd then you multiply the answer with 2 and again try to divide with 2.in short, if you take binary representation of n, iterating from LSB to MSB if 0 comes then it means even number then you do right shift, and if 1 comes then you multiply with 2.=> 2^(no. of set bit).note:- LSB=0 that means an even number and vice-versa