Reverse Integer Problem Solved (C++, Java, Python)

 

Reverse a string is a common question that can be solved through inbuilt functions like a reverse in C++ and Java. The basic idea to solve this type of question is to start your loop from the back and keep storing the values in the new string, but how to do with numbers? In this article, we will try to solve the Reverse Integer Problem.

What is the Reverse Integer problem?

In the Reverse Integer problem, you are given an integer that can lie from [-(2^31), (2^31 – 1)]. You have to reverse its digits and return this new number. If the new integer does not lie between [-(2^31), (2^31 – 1)] return 0.

Here is an example:

Input: -213

Output: -312

Explanation: After reversing 213 we got 312 but as the input is negative return -312

Take this another example:

Input: 1534236469

Output : 0

Explanation: After reversing the digits we got 9646324351 which is greater than (2^31)-1 so we return 0.

Brute Force Approach

The basic approach is to store all the digits of the given integer into an array and after that reverse that array and make a new integer out of it. Here is the process:

1. First, create a vector.
2. Now start pushing the integers into the array by finding the remainder of the given integer with 10, the remainder is the last number. Push this number and divide the given integer by 10.
3. Keep on adding the numbers into the array till the integer becomes 0.
4. Now create a long variable result that will give the result. Assign the result with 0.
5. Start iterating the array and keep on adding this new number at present at the particular index of the array ( result = (result*10) + arr[i] ).
6. If the given integer is negative make result = – result.
7. Return this new result if it lies in the range otherwise return 0. 

The time complexity for the above approach is O(32) ~ O(1). As we keep on dividing the given integer by 10. And maximum number of digits a number can have is 31 as our value lies between [-(2^31), (2^31 – 1)]. The space complexity for the above code is O(31) as we are storing our digits in an array. 

Inbuilt Function Approach

Another way to reverse an integer is to first convert the given integer into a string and then reverse that string through an inbuilt reverse string function. Once the string is reversed again convert the string into the integer. Check if the resultant integer lies in between the range or not. If it does not lie between the range return 0. Otherwise, return the integer.

Let’s examine step by step approach:

1. Create a string s. 
2. Create a boolean variable flag that checks if the given integer is less than 0 or not.
3. Now if the integer is negative make it positive.
4. Change the integer to the string and store it in the string s.
5. Reverse the string s.
6. Store this string into an integer by converting it into an integer.
7. Check if the flag is true or not. If true make the new integer -ve.
8. Check if the integer lies between the range or not if not return 0. Otherwise, return that integer.

The time complexity for the above code is O(32) as we are using the inbuilt function reverse whose time complexity is O(n) where n is the size of the string. As in our case the size will never be more than 32 so the time complexity is O(32). The space complexity for the above code is O(32) as we are using a reverse function which took O(n) space complexity.

Optimized Approach

This approach is the same as the brute force approach. Inside of storing the values in the array we are directly updating our resultant array. Because of this, our space complexity will be reduced from O(32) to O(1). 

1. First, create a long variable result and a boolean variable flag.
2. Check if the integer is negative or not if it is negative make the flag value true.
3. Now keep on adding the remainder of the integer till the integer becomes 0. The result will be ( result  = (result*10) + (num%10)). And make (num = num/10).
4. Now check if the flag is true and make result = – result.
5. Return the result if it lies between the range otherwise return 0.

Let’s examine how we can implement it:

C++ Code

Here is the C++ program to solve the Reverse Integer problem:

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long int num = -241;

    bool flag = false;
    if(num < 0) {
        flag = true;
        num = -num;
    }
    long long int result = 0;

    while(num>0){
        result = (result*10) + (num%10);
        num = num/10;
    }

    if(flag) result = - result;

    if((result > INT_MAX) || (result < INT_MIN)) {
        cout<<0<<endl;
        return 0;
    }

    // result  = -142
    cout<<result<<endl;
    
    return 0;
}

Java Code

Below is how to code it with Java:

class ReverseInteger {
    public static void main(String[] args) {
        long num = -241;

        boolean flag = false;
        if (num < 0) {
            flag = true;
            num = -num;
        }
        long result = 0;

        while (num > 0) {
            result = (result * 10) + (num % 10);
            num = num / 10;
        }

        if (flag) result = -result;

        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
            System.out.println(0);
            return;
        }

        // result  = -142
        System.out.println(result);
    }
}

Python Code

You can do the same with Python also:

num = -241

flag = False
if num < 0:
    flag = True
    num = -num
result = 0

while num > 0:
    result = (result * 10) + (num % 10)
    num = num // 10

if flag:
    result = -result

if result > 2**31 - 1 or result < -2**31:
    print(0)
else:
    # result  = -142
    print(result)

Output:

-142

The time complexity for the above code is O(1). As we are just iterating over the integer whose maximum size is 31 so time complexity will be O(32) ~ O(1). The space complexity is also reduced to O(1).

Let’s compare all the approaches to solve the Reverse Integer problem in the end:

Conclusion

In this article, we discussed the Reverse Integer problem from leetcode. The base case is to check if the number lies between the given range or not. Also, we have to take care of using long variables to store the reverse integer as the integer might overflow which leads to run time error. You can check more programming DSA problems here to practice more.