Algorithms – Reverse Integer

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.

The given algorithm is used to reverse an integer.We are now going through the step-by-step procedure and explain the solution.

1. Initialize a long variable called reversedInteger to store the reversed value. Using a long type allows handling larger numbers without overflow.
2. Enter a while loop that continues until the input integer x becomes zero.
3. Inside the loop, the current least significant digit of x is obtained by taking the remainder when divided by 10 (i.e., x % 10). This digit is then added to the reversedInteger after shifting it one place to the left and making space for the new digit (i.e., reversedInteger * 10 + x % 10).
4. After updating the reversedInteger, divide x by 10 (i.e., x = x / 10) to remove the least significant digit from x and prepare for the next iteration.
5. Once x becomes zero, exit the while loop.
6. Check if the reversed integer reversedInteger is within the range of the int data type, specifically between Integer.MIN_VALUE and Integer.MAX_VALUE. If it is within this range, cast reversedInteger to int and return the result. Otherwise, return 0.

Now, let’s discuss the space and time complexity of this algorithm:

Space complexity

As you can see, the algorithm only uses a constant amount of extra space, regardless of the input size. It only requires a few variables to store the intermediate values, so the space complexity is O(1) (constant)

Time Complexity

The time complexity of this algorithm is determined by the number of digits in the input integer x. Let’s denote the number of digits as n. In the worst case, the algorithm needs to iterate through all the digits of x. Since the number of digits in x is proportional to the logarithm of x (base 10), we can say the time complexity is O(log(x)).

Solution

public int reverse(int x) {

        long reversedInteger = 0;

        while(x != 0){
            reversedInteger = reversedInteger * 10 + x%10;
            x= x/10;
        }

       return reversedInteger > Integer.MIN_VALUE && reversedInteger < Integer.MAX_VALUE ? (int) reversedInteger : 0;

    }