nitin12384's blog

Intution behind simple solution of this problem.
By nitin12384, history, 3 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply