medium Reverse Integer

Problem Statement

Given a signed 32-bit integer x, return the reverse of x. If the reversed value of x goes beyond the signed 32-bit integer range [-2³¹, 2³¹ - 1], then return 0.

A reverse of x should not contain leading zeros.

Examples

• Example 1:

  • Input: x = 123
  • Expected Output: 321
  • Justification: Reversing the digits of 123 results in 321, which is within the 32-bit signed integer range.

• Example 2:

  • Input: x = -456432
  • Expected Output: -234654
  • Justification: Reversing the digits of -456432 results in -234654, maintaining the negative sign and staying within the 32-bit signed integer range.

• Example 3:

  • Input: x = 1200
  • Expected Output: 21
  • Justification: Reversing the digits of 1200 results in 0021, but leading zeros are dropped, resulting in 21.

Solution

To solve this problem, we'll take a mathematical approach to reverse the digits of the given integer. This approach is effective because it directly manipulates the numerical value, allowing us to easily handle both positive and negative numbers and check for overflow conditions. The essence of the solution is to iteratively extract the last digit of the current number, append it to the reversed number, and then remove that digit from the original number by division. This process repeats until all digits have been processed.

The key to handling overflow is to check if the new reversed number, when multiplied back by 10 (to add a new digit), would exceed the 32-bit integer limit. By performing this check before actually appending the next digit, we can ensure that our function never produces an overflowed result. This method is not only straightforward but also efficient, as it requires no additional data structures and operates in linear time complexity relative to the number of digits in the input.

Step-by-step Algorithm

• Initialize a variable reversed to store the reversed number, starting at 0.
• While the input number x is not 0:
  • Extract the last digit of x by taking x % 10.
  • Check for overflow/underflow before appending the digit to reversed. If appending would cause overflow or underflow, return 0.
  • Append the digit to reversed by multiplying reversed by 10 and adding the extracted digit.
  • Remove the last digit from x by dividing it by 10.
• After the loop, if reversed is within the 32-bit signed integer range, return reversed. Otherwise, return 0.

Algorithm Walkthrough

Let's consider the Input: -456432

1. Initialize Variables:

   • Set reversed to 0. This variable will hold our reversed number as we build it.
   • The input x is (-456432).

2. Iteration 1:

   • Extract the last digit: (x % 10 = -2).
   • Append -2 to reversed: (reversed = reversed * 10 - 2 = -2).
   • Update x by removing the last digit: (x = x / 10 = -45643).

3. Iteration 2:

   • Extract the last digit: (x % 10 = -3).
   • Append -3 to reversed: (reversed = -2 * 10 - 3 = -23).
   • Update x: (x = x / 10 = -4564).

4. Iteration 3:

   • Extract the last digit: (x % 10 = -4).
   • Append -4 to reversed: (reversed = -23 * 10 - 4 = -234).
   • Update x: (x = x / 10 = -456).

5. Iteration 4:

   • Extract the last digit: (x % 10 = -6).
   • Append -6 to reversed: (reversed = -234 * 10 - 6 = -2346).
   • Update x: (x = x / 10 = -45).

6. Iteration 5:

   • Extract the last digit: (x % 10 = -5).
   • Append -5 to reversed: (reversed = -2346 * 10 - 5 = -23465).
   • Update x: (x = x / 10 = -4).

7. Iteration 6:

   • Extract the last digit: (x % 10 = -4).
   • Append -4 to reversed: (reversed = -23465 * 10 - 4 = -234654).
   • Update x: (x = x / 10 = 0).

8. Final Check and Return:

   • At this point, x is 0, so we exit the loop.
   • Return reversed, which is (-234654).

Code

public class Solution {

  public int reverse(int x) {
    int reversed = 0; // To hold the reversed number
    while (x != 0) { // Continue until x becomes 0
      int digit = x % 10; // Extract the last digit
      int newReversed = reversed * 10 + digit; // Append the digit to the reversed number
      // Overflow check: if the operation reverses when reversed, overflow occurred
      if ((newReversed - digit) / 10 != reversed) return 0;
      reversed = newReversed; // Update the reversed number
      x /= 10; // Remove the last digit from x
    }
    return reversed; // Return the reversed number
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.reverse(123));
    System.out.println(solution.reverse(-456432));
    System.out.println(solution.reverse(1200));
  }
}

Complexity Analysis

Time Complexity

The time complexity of the reverse integer algorithm is , where (n) is the value of the input integer. This is because the algorithm processes each digit of the input number exactly once, and the number of digits in a number (n) is proportional to .

Space Complexity

The space complexity of the algorithm is , indicating constant space usage. This is because the algorithm uses a fixed amount of space (a few variables) regardless of the input size.