7. Reverse Integer

MediumMath
Leetcode Link

Problem Description

The task is to take a signed 32-bit integer x and reverse the order of its digits. For example, if the input is 123, the output should be 321. If the input is -123, the output should be -321. The tricky part comes with the boundaries of a 32-bit signed integer, which ranges from -2^31 to 2^31 - 1. If reversing the digits of x would cause the number to fall outside this range, the function should return 0 instead. This means we need to be careful with overflow—an issue that occurs when the reversed integer is too large or too small to be represented by a 32-bit signed integer.

Intuition

To solve this problem, we first set up two boundaries, mi and mx, which represent the minimum and maximum values of a 32-bit signed integer, respectively. These values are -2^31 and 2^31 - 1.

We want to build the reversed number digit by digit. We can isolate the last digit of x by taking x % 10 (the remainder when x is divided by 10). This last digit, referred to as y in our code, is the next digit to be placed in the reversed number.

However, we need to be careful not to cause an overflow when we add this new digit to the reversed number. Before we add y to the reversed number ans, we check if adding the digit would cause an overflow. To do this, we check if ans is either less than mi / 10 + 1 or greater than mx / 10. If it's outside this range, we return 0.

If it's safe to add the digit, we proceed. We add the digit to ans by multiplying ans by 10 (which "shifts" the current digits to the left) and then adding y. This process effectively reverses the digits of x.

For the next iteration, we need to remove the last digit from x. We do this by subtracting y from x and then dividing by 10.

We repeat this process until x has no more digits left. The result is a reversed number that fits within the 32-bit signed integer range, or 0 if an overflow would have occurred.

The time complexity is O(\log |x|) because the process continues for as many digits as x has, and the space complexity is O(1) as there is a constant amount of memory being used regardless of the size of x.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does merge sort divide the problem into subproblems?

Solution Approach

The implementation uses a straightforward algorithm that iterates through the digits of the input number x and constructs the reversed number without using additional data structures or complex patterns. Let's detail the steps using the provided Reference Solution Approach:

  1. Initialization: We start by setting the initial reversed number ans to 0. We also define the minimum and maximum values mi and mx for a 32-bit signed integer, which are -2^31 and 2^31 - 1.

  2. Reversing Digits: The while loop runs as long as there are digits left in x. Within the loop, we take the following steps:

    • Isolate the last digit y of x by computing x % 10.
    • If x is negative and y is positive, adjust y by subtracting 10 to make it negative.

  3. Checking for Overflow: Before appending y to ans, we must confirm that ans * 10 + y will not exceed the boundaries set by mi and mx. To avoid overflow, we check:

    • If ans is less than mi/10 + 1 or greater than mx/10, we return 0 immediately, as adding another digit would exceed the 32-bit signed integer limits.

  4. Building the Reversed Number: If it is safe to proceed, we multiply ans by 10 (which shifts the reversed number one place to the left) and add y to ans. This action reverses y from its position in x to its new reversed position in ans.

  5. Updating the Original Number x: We update x by removing its last digit. This is done by subtracting y from x and then dividing by 10.

  6. Completion: The loop repeats this process, accumulating the reversed number in ans until all digits are processed.

The core of this approach is predicated on the mathematical guarantees regarding integer division and modulus operations in Python. The guard checks for overflow by considering both scale (multiplication by 10) and addition (adding the digit) separately and only proceeds if the operation stays within bounds.

By following the constraints of a 32-bit signed integer at every step and efficiently using arithmetic operations, the reverse function achieves the reversal of digits robustly and efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

To illustrate the solution approach, let's take x = 1469 as our example.

  1. Initialization:

    • ans is initialized to 0.
    • mi is set to -2^31 (-2147483648).
    • mx is set to 2^31 - 1 (2147483647).

  2. Reversing Digits: Begin while loop with x = 1469.

    • Isolate the last digit y by computing 1469 % 10 = 9.
    • x is positive so we keep y = 9.

  3. Checking for Overflow:

    • ans is currently 0, which is greater than mi/10 + 1 (-214748364) and less than mx/10 (214748364), so continue without returning 0.

  4. Building the Reversed Number:

    • We multiply ans by 10, which is still 0, and add y to get ans = 9.

  5. Updating the Original Number x:

    • Update x to remove the last digit: x = (1469 - 9) / 10 which simplifies to x = 146.

Next iteration of the loop with x = 146:

  • Isolate y = 146 % 10 = 6.
  • Check for overflow: ans = 9 is still within bounds.
  • Update ans: ans = 9 * 10 + 6 = 96.
  • Update x: x = (146 - 6) / 10 which simplifies to x = 14.

Next iteration with x = 14:

  • Isolate y = 14 % 10 = 4.
  • Check for overflow: ans = 96 is still within bounds.
  • Update ans: ans = 96 * 10 + 4 = 964.
  • Update x: x = (14 - 4) / 10 which simplifies to x = 1.

Final iteration with x = 1:

  • Isolate y = 1 % 10 = 1.
  • Check for overflow: ans = 964 is still within bounds.
  • Update ans: ans = 964 * 10 + 1 = 9641.
  • Update x: x = (1 - 1) / 10 which simplifies to x = 0.

Now x = 0, the while loop terminates, and the reversed number ans = 9641 is returned. There were no issues with overflow throughout the process, so the result 9641 is the correct reversed integer for our example of x = 1469.

This process demonstrates that by evaluating the overflow conditions before each digit is added to the reversed number, and by building the reversed number step by step, it's possible to safely reverse the digits of x without using extra space or complex data structures. Additionally, due to the use of modulo and division operations, the solution efficiently handles the reversal process for each digit.

Solution Implementation

1class Solution:
2    def reverse(self, x: int) -> int:
3        # This variable will hold the reversed number
4        reversed_number = 0
5      
6        # These define the range of acceptable 32-bit signed integer values
7        min_int, max_int = -2**31, 2**31 - 1
8      
9        while x:
10            # Check if the reversed_number will overflow when multiplied by 10
11            if reversed_number < min_int // 10 + 1 or reversed_number > max_int // 10:
12                # Return 0 on overflow as per problem constraints
13                return 0
14          
15            # Extract the least significant digit of the current number
16            digit = x % 10
17          
18            # Adjustments for negative numbers when the extracted digit is non-zero
19            if x < 0 and digit > 0:
20                digit -= 10
21          
22            # Shift reversed_number digits to the left and add the new digit
23            reversed_number = reversed_number * 10 + digit
24          
25            # Remove the least significant digit from x
26            x = (x - digit) // 10
27      
28        # Return the reversed number within the 32-bit signed integer range
29        return reversed_number
30
1class Solution {
2    public int reverse(int x) {
3        // Initialize answer to hold the reversed number
4        int reversedNumber = 0;
5      
6        // Loop until x becomes 0
7        while (x != 0) {
8            // Check for overflow/underflow condition, return 0 if violated
9            // Integer.MIN_VALUE is -2^31 and Integer.MAX_VALUE is 2^31 - 1
10            if (reversedNumber < Integer.MIN_VALUE / 10 || reversedNumber > Integer.MAX_VALUE / 10) {
11                return 0;
12            }
13          
14            // Add the last digit of x to reversedNumber
15            reversedNumber = reversedNumber * 10 + x % 10;
16          
17            // Remove the last digit from x
18            x /= 10;
19        }
20      
21        // Return the reversed number
22        return reversedNumber;
23    }
24}
25
1#include <climits> // For INT_MIN and INT_MAX
2
3class Solution {
4public:
5    int reverse(int x) {
6        int reversedNumber = 0;
7      
8        // Loop until all digits are processed
9        while (x != 0) {
10            // Check if multiplying by 10 will cause overflow
11            if (reversedNumber < INT_MIN / 10 || reversedNumber > INT_MAX / 10) {
12                return 0;  // Return 0 if overflow would occur
13            }
14          
15            // Pop the last digit from 'x' using modulus and add it to 'reversedNumber'
16            reversedNumber = reversedNumber * 10 + x % 10;
17          
18            // Remove the last digit from 'x' by dividing it by 10
19            x /= 10;
20        }
21      
22        return reversedNumber;  // Return the reversed number
23    }
24};
25
1/**
2 * Reverse an integer.
3 * @param {number} x - The integer to be reversed.
4 * @return {number} - The reversed integer, or 0 if the reversed integer overflows 32-bit signed integer range.
5 */
6const reverseInteger = (x: number): number => {
7    // Define the minimum and maximum values for 32-bit signed integer.
8    const INT_MIN: number = -(2 ** 31);
9    const INT_MAX: number = 2 ** 31 - 1;
10
11    let reversed: number = 0;
12
13    while (x !== 0) {
14        // Check for potential overflow by comparing with pre-divided limits.
15        if (reversed < Math.floor(INT_MIN / 10) || reversed > Math.floor(INT_MAX / 10)) {
16            return 0;
17        }
18
19        // Perform the reverse by multiplying the current reversed by 10 and adding the last digit of x.
20        reversed = reversed * 10 + (x % 10);
21
22        // Floor division by 10 to get the next digit (in TypeScript `~~` is replaced by Math.trunc).
23        // Since x can be negative, we use trunc instead of floor to correctly handle negative numbers.
24        x = Math.trunc(x / 10);
25    }
26
27    return reversed;
28};
29
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

Time Complexity

The time complexity of the given code is dependent on the number of digits in the integer x. Since we are handling the integer digit by digit, the number of operations is linearly proportional to the number of digits. If the integer x has n digits, then the time complexity is O(n).

Space Complexity

The space complexity of the provided code is O(1). This is because we are only using a fixed amount of additional space (ans, mi, mx, y, and a few variables for control flow) regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫