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 : https://discuss.codechef.com/t/official-basic-math-combinatorics-problems/65236/16
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