GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
293 views

A palindrome is a string whose reversal is identical to the string. How many bit strings of length n are palindromes?

  1.   2⌈n⁄2⌉
  2.   2(⌊ n/2⌋ )
  3.   2⌈n⁄2⌉ -1
  4.   2(⌊ n/2⌋) -1
asked in Combinatory by Veteran (13.4k points)  
retagged by | 293 views

2 Answers

+3 votes

Try with N= 2 you get aa,bb 2⌈n⁄2⌉  = 2

Try with N= 3 you get aaa,bbb ,aba , bab  2⌈n⁄2⌉  = 4

Try with N= 4 you get aaaa,bbbb ,abba , baab , 2⌈n⁄2⌉  = 4

A is answer

answered by Veteran (49.3k points)  
0 votes

The trick here is to realize that a palindrome of length n is completely determined by its first ceiling(n/2)  bits.
This is true because once these bits are specified, the remaining bits, read from right to left, must be identical
to the first floor(n/2) bits, read from left to right. Furthermore, these first ceiling(n/2) bits can be specified at will,
and by the product rule, there are 2^ceiling(n/2) ways to do so. Hence answer is 2^ceiling(n/2)--> Option (A)

answered by (369 points)  
for even length its right

but for odd length N=3 how come ur getting 4??

considering aba..it can only be two ways

that is position of a can be in two places

so for odd it should be floor(n/2) right??

please correct me

Related questions



Top Users Sep 2017
  1. Habibkhan

    8312 Points

  2. Warrior

    2862 Points

  3. rishu_darkshadow

    2796 Points

  4. Arjun

    2766 Points

  5. A_i_$_h

    2526 Points

  6. manu00x

    2094 Points

  7. nikunj

    1980 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1810 Points

  10. SiddharthMahapatra

    1718 Points


26,283 questions
33,842 answers
80,383 comments
31,193 users