Problem Statement
Implement the function boolean isPalindrome (int n);
Which will return true if the bit-wise representation of the integer
is a palindrome and false otherwise.
Motivation: This is a favorite interview question of Amazon guys.
Solution:
The idea is simple, we take two pointers one at leftmost bit and another at rightmost bit, extract bits information using the pointers both bits should either be 0 or 1. and move the pointers until they meet.
Now how would you extract the bit is tricky one, basically you first get number of bits in the integer and then shift 1 left by (number of bits -1) this will become our leftmost pointer and number 1 will be our rightmost pointer. Use & operator between original number and these pointers if the result is 0 then the corresponding bit is zero else(non-zero) then corresponding bit is 1.
Note: check for non-zero rather then > 0 as 1000000000000 will be negative.
Here is the java code to get the size of the integer
1 2 3 4 5 6 7 8 9 10 | public int getSizeOfInteger(){ int size =1; int num =1; //shift the number untill it becomes negative(1 followed by 0's) while(num > 0){ num = num<<1; size++; } return size;} |
Here is the java code to get if the bit representation of the number is palindrome or not
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public boolean isPalindrome(int n){ int rightPointer =1; int leftPointer = 1<<(getSizeOfInteger()-1); int count = getSizeOfInteger()/2; while(count > 0){ //Checking if both bits are 0 or both are non-zero and then negate if( !(((n & leftPointer) != 0 && (n & rightPointer) != 0) || ( (n & leftPointer) == 0 && (n & rightPointer) == 0))){ return false;//Both bits are not same } count--; } return true;} |
Facebook Comments
can we do this que as..take the reverse of the no n dn compare if the reverse n original no are equal , then its a palindrome otherwise not…
Yes that will also be correct, but it will be higher in complexity and space.