Reverse Integer Problem

Problem

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Examples

Example1:

x = 123,
return 321

Example2:

x = -123,
return -321

Solution

Method 1 - Convert Number to String and Reverse

We can convert the integer to a string/char array, reverse the order, and convert the string/char array back to an integer. However, this will require extra space for the string. It doesn’t seem to be the right way, if you come with such a solution.

❌ Problem - 64 Bit integer not allowed

Method 2 - Using Mod and Divide

For Reversing the integer, we can use mod operator to extract the digit and reverse it by multiplying by 10.

For eg. 123

123%10 = 3
rev = 3 * 10^0 = 3
num = num / 10 = 12

12 % 10 = 2
rev = rev * 10^1 +2 = 30 + 2 = 32
num = num /10 = 1

1 % 10 = 1
rev = rev * 10^2 + 1 = 320 + 1 = 321

Here is the code:

public int reverse(int x) {
	int rev = 0;
	while (x != 0) {
		rev = rev * 10 + x % 10;
		x = x / 10;
	}

	return rev;
}

❌ Problem - Will not handle overflow

Handling Integer Out of Bound Case

We can use 64bit integer to store reverse.

public int reverse(int x) {
	long rev = 0;
	while (x != 0) {
		rev = rev * 10 + x % 10;
		x = x / 10;
	}
	if (rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE)
		return 0;
	else
		return (int) rev;
}

❌ Problem - 64 Bit integer not allowed

Handling Integer Out of Bound without 64 Bit Integers 🏆

Now this becomes challenging, we have to pre-empt adding digit to reversed number. Before adding check if we are overflowing. We know integer min value = -2147483648 and max value = 2147483647.

Here is the code:

public int reverse(int x) {
	int rev = 0;
	int min = Integer.MIN_VALUE / 10; // -214748364
	int minLastDigit = Integer.MIN_VALUE % 10; // -8
	int max = Integer.MAX_VALUE / 10; // 214748364
	int maxLastDigit = Integer.MAX_VALUE % 10; // 7
	while (x != 0) {
		int digit = x % 10;
		x = x / 10;

		if (rev > max || (rev == max && digit >= maxLastDigit )) {
			return 0;
		}
		if (rev < min || (rev == min && digit <= minLastDigit )) {
			return 0;
		}
		rev = rev * 10 + digit;
	}

	return rev;
}