Algo #120 : Pallindrome Check

Problem Statement : 
         Check if a number is palindrome without extra space O(1) .

Solution : 

      One of the common ways i have seen interviewees approach to this problem is by converting it into a string , but the constraint of the problem doesn't allow you to use extra space.

Here we will use pointers to check for palindrome but without converting it into a string.

Iterative Implementation :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

boolean isPalindrome(int num) { int div = 1; if(num < 0) num = -num; for(;num/div>=10;div *=10); //div which will help in dividing below, [Note : dont Miss ';'] while (num != 0) { int leftDigit = num / div; int rightDigit = num % 10; if (leftDigit != rightDigit) return false; num %= div ; //removes left most digit num /= 10 ; //removes right most digit div /= 100; } return true; }

 Recursive Implementation :
 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

/** * Recursive apporach to check if a number is pallindrome without extra space * @author prathore2 */ public class PallindromeCheck { private static int dummy = 0; public static boolean isPallindrome(int num) { dummy = num; return isPallindrome1(num); } private static boolean isPallindrome1(int num) { if (num == 0) return true; if (isPallindrome1(num / 10) && (num % 10 == dummy % 10)) { dummy /= 10; return true; } return false; } public static void main(String[] args) { System.out.println(isPallindrome(12321)); } }

Please post your comment and suggestions if any.
Happy Coding !! :)