7. Reverse Integer

Problem description

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 [-231, 231 - 1], then return 0.

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

Solution

Given a signed 32-bit integer x, the task is to reverse the digits of x and return the result. If reversing the integer causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 – 1], then the function should return 0.

Step by step algorithm

1. Initialize a variable called “result” to 0.
2. Use a while loop to repeatedly extract the last digit of the given integer by using the modulo operator (x % 10), add this digit to result multiplied by 10 (result * 10), and then update the value of x by dividing it by 10 (x /= 10).
3. If the result is greater than or equal to 2^31 – 1 or less than or equal to -2^31, return 0. This is because reversing the integer could cause it to go outside the signed 32-bit integer range [-231, 231 – 1].
4. If the result is within the correct range, return the result as the reversed integer.

C#

public int Reverse(int x)
{
    int rev = 0;
    while (x != 0)
    {
        int pop = x % 10;
        x /= 10;
        if (rev > int.MaxValue/10 || (rev == int.MaxValue / 10 && pop > 7)) return 0;
        if (rev < int.MinValue/10 || (rev == int.MinValue / 10 && pop < -8)) return 0;
        rev = rev * 10 + pop;
    }
    return rev;
}

C++

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

JS

var reverse = function(x) {
    let rev = 0;
    while (x !== 0) {
        let pop = x % 10;
        x = Math.floor(x / 10);
        if (rev > 214748364 || (rev === 214748364 && pop > 7)) return 0;
        if (rev < -214748364 || (rev === -214748364 && pop < -8)) return 0;
        rev = rev * 10 + pop;
    }
    return rev;
};

Python

class Solution:
    def reverse(self, x: int) -> int:
        rev = 0
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        while x != 0:
            pop = x % 10
            x //= 10
            if rev > INT_MAX//10 or (rev == INT_MAX//10 and pop > 7):
                return 0
            if rev < INT_MIN//10 or (rev == INT_MIN//10 and pop < -8):
                return 0
            rev = rev * 10 + pop
        return rev

Time and space complexity

Time Complexity: O(log(n)), where n is the number of digits in the input integer. The solution iterates through the digits of the input integer and reverses it, taking O(log(n)) time to reverse the integer.

Space Complexity: O(1), as the solution uses a single integer variable to store the reversed integer.

Conclusion:

In this blog post, we have seen a step-by-step algorithm to reverse an integer in four different programming languages, namely C#, C++, JavaScript, and Python. The solution is simple and efficient

0

0