implement isPalindrome(int n)

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

	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

	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