Scala Interview Question – Palindrome Number

Problem Statement

Given a 32-bit signed integer, determine whether that integer is a palindrome. Do this without converting it to string.

Solution

The first idea that comes to mind is to convert the number into string, and check if the string is a palindrome by using builtin string reverse function, but this is not allowed by the problem description, so second idea would be reversing the number itself as done in this post and then compare the number with original number, if they are the same, then the number is a palindrome. However, if the reversed number is larger than Integer.MAX_VALUE, we will hit integer overflow problem.

Following the thoughts based on the second idea, to avoid the overflow issue of the reverted number, what if we only revert half of the  number? After all, the reverse of the last half of the palindrome should be the same as the first half of the number, if the number is a palindrome.

For example, if the input is 1221, if we can revert the last part of the number “1221” from “21” to “12“, and compare it with the first half of the number “12”, since 12 is the same as 12, we know that the number is a palindrome. When the length is an odd number, we can get rid of the middle digit by revertedNumber/10, for example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123, since the middle digit doesn’t matter in palindrome(it will always equal to itself), we can simply get rid of it.

def isPalindrome(x: Int) : Boolean = {
  var input = x
  var rev: Int = 0

  while(input > rev)          // for space optimizing and avoiding overflow issue
  {
    rev = rev * 10 + input % 10
    input = input/10
  }

  rev==input || input==rev/10 // for handling odd number of digits
}

Test Cases

isPalindrome(1221)
isPalindrome(12321)
isPalindrome(2147483647)

Complexity Analysis

  • Time complexity : O(log10n). We divided the input by 10 for every iteration, so the time complexity is O(log10n)
  • Space complexity : O(1)