*Note- First binary number whose representation is a palindrome is 1.

Understanding the Problem:

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

ODD LENGTH-

Say L = 5. Now the palindrome must be of the form "abcde" to be a binary string of length 5 a must be 1 and to be a 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 ('b' and 'c') which we can alter. This can be done in 2^{2}=4 ways i.e. from 00 - 11.

Hence palindromes for length 5 can be 10001, 10101, 11011, and 11111.

EVEN LENGTH-

For length L = 10 we can have palindromes of the form, "abcdeedcba" so we can have 2^{4} = 16 palindromes possible.

So we have 4 places ('b', 'c', 'd' and 'e') which we can alter. This can be done in 16 ways i.e. from 0000 - 1111.

If we use the above process for all the lengths, we get the following:

In figure 3, we see that length 1 and 2 have 1 binary palindrome.

Length 3 has 2 binary palindromes which look like 1_1. In this space we can put either 0 or 1.

Similarly, the binary palindromes of other lengths are given too. This list goes on.

Hence, the number of palindromes in a string of length l is 2^{(l-1)/2}.

It is very important for you to watch the solution video to understand the above explained procedure.

APPROACH :

You have seen in figure 3 that the palindromes 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 110_ _1.

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

CODE

We begin with coding this problem now by making use of the above discussion.

import java.io.*;
import java.util.*;
public class Main {
public static int getRev(int n){
int rev=0;
while(n!=0){
int lb=(n&1);
rev|=lb;
rev<<=1;
n>>=1;
}
rev>>=1;
return rev;
}
public static int NthPalindromicBinary(int n) {
int count=1;
int len=1;
while(count< n){
len++;
int elementsForThisLen= (1<<(len-1)/2);
count+=elementsForThisLen;
}
count-=(1<<(len-1)/2);
int offset=n-count-1;
int ans=(1<<(len-1));
ans |= (offset<<(len/2));
int valPR= (ans>>(len/2));
int rev= getRev(valPR);
ans|=rev;
return ans;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
System.out.println(NthPalindromicBinary(n));
}
}

java;
true";

Analysis

Time Complexity:

O(1)

Space Complexity:

O(1)

With this we conclude the question "Nth Palindromic Binary" and the topic "Bit Manipulation".

In case you have any doubts in this article, we suggest you watch its solution video.