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.