Scala Interview Question – Reverse Integer

Problem Statement

Given a 32-bit signed integer, determine its reverse. Since we can have signed integer we can have negative values, so for Input => -123 Output => -321, also need to take care of Overflow cases which should results in Output => 0 (Invalid).

Solution

The first idea that comes to mind is to convert the number into string, and reverse the string using builtin reverse function. we also have to take care of properly handling negative inputs. Overflow case is also handled by comparing resulting number with Integer min and max value.

def reverse(x: Int): Int = {
  val isNegative = if (x < 0) 1 else 0

  val y = if (isNegative == 1) (x.toLong*(-1)).toString.reverse else x.toString.reverse

  if (y.toLong > Int.MaxValue || y.toLong < Int.MinValue ) // Overflow case
    0
  else {
    if (isNegative == 1) y.toInt * (-1) else y.toInt
  }
}

Now this approach would require extra non-constant space for creating the reverse string which might not be allowed. So lets think about another approach. Lets take this number 1234, if we do 1234 % 10, we get the last digit 4, to get the second to the last digit, we need to remove the last digit from 1234, we could do so by dividing it by 10, 1234 / 10 = 123. Then we can get the last digit again by doing a modulus by 10, 123 % 10 = 3, and if we multiply the last digit by 10 and add the second last digit, 4 * 10 + 3 = 43, it gives us the reverted number we want. Continuing this process would give us the reverted number.

def reverse(x: Int): Int = {
  var output : Long = 0;
  var input = x    // method parameters are always VAL, hence convert it into VAR

  while(input != 0){
    output = output * 10 + input % 10;
    input = input/10;

    if( output > Integer.MAX_VALUE || output < Integer.MIN_VALUE)   // Overflow case
      return 0;
  }

  output.toInt
}

Test Cases

reverse(123456)
reverse(-123)

Int.MaxValue
Int.MinValue
Long.MaxValue.toString

reverse(2147483641)
reverse(2147483647)
reverse(-2147483648)

Complexity Analysis

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