Nth Palindromic Binary

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given an integer N.
2. You have to find the N-th number whose binary representation is a palindrome.

Note -> First binary number whose representation is a palindrome is 1.
Input Format
A number N
Output Format
Check the sample output and question video.
Question Video
Constraints
1 <= n <= 2*10^4
Sample Input
17
Sample Output
85


  • Editorial

    In this problem, we are given an integer number N and we need to find the corresponding Nth Palindromic Binary Number.

    For example: N = 1 => 1

    N = 2 => 3

    N = 5 => 9

    To understand the problem better we need to understand the nature of palindrome for a string of length L.

    Say L = 5 => abcde to be a binary string of length 5 a must be 1 and to be palindrome e must be equal to a. So now we have our string as 1bcd1. Also, d must be equal to b. So string equals 1bcb1. So we have only two places which we can alter which can be done in 22 = 4 ways i.e. from 00 - 11. Hence palindromes for length 5 can be 1 0 0 0 1, 1 0 1 0 1, 1 1 0 1 1, and 1 1 1 1 1.

    Similarly, for length L = 10 we can have palindromes of the form:

    1 _ _ _ _ * * * * 1 so we can have 24 = 16 palindromes possible.

    For length L = 7 we can have palindromes of the form:

    1 _ _ _ * * 1 so we can have 23 = 8 palindromes possible.

    Hence, the number of palindromes in a string of length n is 2(n-1)/2.

    Now suppose we wish to find N = 13th palindromic binary so we need to know two things first the length of the string at that position and then the offset, which is the position of this binary in its length group.

    So firstly to calculate the group, we will start with len = 1 and count = 1 and iterate till count < N and for every iteration, we will update the len and add its number of palindromes by the formula 2(n-1)/2

    Now to calculate offset, it can be calculated by subtracting N from the last group count (or position).

    For N = 13,

    Len = 1 count = 1

    Len = 2 count = 2

    Len = 3 count = 4

    Len = 4 count = 6

    Len = 5 count = 10

    Len = 6 count = 14 > 13 break

    Count = count - 2(len-2)/2 = 10

    Offset = 13 - 10 - 1 = 2

    By doing this we get information that our string is of type

    1 b c c b 1

    And its position is 2.

    Insight: Observe the following palindromes-

    ----------------------

    1 -> 1

    ----------------------

    2 -> 1 1

    ----------------------

    3 -> 1 0 1

    4 -> 1 1 1

    ----------------------

    5 - > 1 0 0 1

    6 -> 1 1 1 1

    ----------------------

    7 -> 1 0 0 0 1

    8 -> 1 0 1 0 1

    9 -> 1 1 0 1 1

    10 -> 1 1 1 1 1

    ----------------------

    11 -> 1 0 0 0 0 1

    12 -> 1 0 1 1 0 1

    13 -> 1 1 0 0 1 1

    14 -> 1 1 1 1 1 1

    ----------------------

    The palindromes above are divided into their groups which are decided by the length of the palindrome. Now if we observe we can notice for any group having size say k then its left half elements are of the type:

    1 [ 0 - (k-1) ]

    For example group 6 from 11 -14 are of the type:

    1 0 0

    1 0 1

    1 1 0

    1 1 1

    Which is the same as [0 - 3] in binary.

    Therefore the value of offset received is equal to the binary representation to be displayed in that palindrome.

    So for N = 13 we have offset = 2 so we would have a string as 1 1 0 _ _ 1

    Now to fill up the remaining space we just need to do XOR with the reverse of the answer so far.

    Time Complexity: O(1)

    The time complexity for the function is constant.

    Space Complexity: O(1)

    The space complexity for the function is constant.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name