Redirecting to
NADOS


  Prev   Next

Nth PALINDROMIC BINARY







Practice doesn't make perfect.
Practice reduces the imperfection.

Nth PALINDROMIC BINARY

Howdy coder. We are going to solve the last question under Bit Manipulation in this article. We hope you are looking forward to it.

Reader, first go through the outline of the problem to understand it better.

You are given an integer N and have to find the Nth number whose binary representation is a palindrome.


Important Links : Problem Link, Solution Video


*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 22=4 ways i.e. from 00 - 11.
  • Hence palindromes for length 5 can be 10001, 10101, 11011, and 11111.
    img

EVEN LENGTH-

  • For length L = 10 we can have palindromes of the form, "abcdeedcba" so we can have 24 = 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.
    • img

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

img

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.

Nth Palindromic Binary
Bit Manipulation
Author: Shreeya Gupta
 
Run
Id Name