5 Jul 2015

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 !! :)

1 comment:

  1. We don't have to worry about type conversion if we go with a language that supports dynamic-typing. :)

    Here's an implementation in Perl:

    #!/usr/bin/perl

    use strict;
    use warnings;

    my $str = $ARGV[0];
    chomp $str;

    print is_palindrome($str),"\n";

    sub is_palindrome {
    my $str = shift;

    my $i = 0;
    my $j = length($str) - 1;
    while ($i <= $j) {
    return "no" if (substr($str, $i, 1) ne substr($str, $j, 1));
    $i++; $j--;
    }
    return "yes";
    }

    ReplyDelete