CODEWITHSUNDEEP
javaalgorithmintegerreverse
Rohan Sharma
Rohan Sharma

Reputation: 55

Reverse Integer (Leetcode)

I was trying to solve 7.Reverse Integer on leetcode https://leetcode.com/problems/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 [-2^31, 2^31 - 1], then return 0.

Example 1:

Input: x = 123  
Output: 321

My solution for the above problem is

class Solution {  
    public int reverse(int x) {  
        int num=0;  
        if(x>Integer.MAX_VALUE||x<Integer.MIN_VALUE) return 0;  
        while(x!=0){  
            int a=x%10;  
            num=num*10+a;  
            x=x/10;  
            
            
        }  
        return num;  
    }  
}

I'm getting 4 test cases wrong. One of which is :

Example

Input: 1534236469  
Output : 1056389759  
Expected: 0

Upvotes: 0

Views: 1556

Answers (4)

vacawama
vacawama

Reputation: 154583

Your problem is that the overflow is in the num variable and you are not checking for that. By adding a check to make sure the calculation will not overflow before performing num = num * 10 + a, you can return 0 when necessary.

Also, you weren't handling negative numbers properly. A check for a negative up front can allow you to work with a positive number and then just negate the result.

class Solution {  
    public int reverse(int x) {  
        int num = 0;  
        Boolean negative = false;
        
        if (x == Integer.MIN_VALUE) return 0;
        if (x < 0) {
            x = -x;
            negative = true;
        }
        while (x != 0) {  
            int a = x % 10; 
            // Check if the next operation is going to cause an overflow
            // and return 0 if it does
            if (num > (Integer.MAX_VALUE - a) / 10) return 0;
            num = num * 10 + a;  
            x = x / 10;  
        }  
        return negative ? -num : num;  
    }  
}

Upvotes: 3

trincot
trincot

Reputation: 350252

You're not dealing with the theoretical signed 32-bit integer overflow that might occur in the loop, meaning you'll sometimes return a number outside of that range. Also, the logic will not work as expected with negative values.

And to be really precise on the restriction of signed 32-bit, special care needs to be taken when the input is -231, as its absolute value does not represent a valid signed 32-bit integer.

class Solution {
    public int reverse(int x) {
        if (x < 0) return x == -2147483648 ? 0 : -reverse(-x);
        int res = 0;
        while (x > 0 && res < 214748364) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return x == 0 ? res
             : res > 214748364 || x > 7 ? 0
             : res * 10 + x;
    }
}

Upvotes: 2

JaNith RathNayaka
JaNith RathNayaka

Reputation: 163

Input: 123 Output: 321 Input: -123 Output: -321 Input: 120 Output: 2

class Solution { public: int reverse(int x) {

    int rev = 0;

    constexpr int top_limit = INT_MAX/10;

    constexpr int bottom_limit = INT_MIN/10;

    while (x) {

        if (rev > top_limit || rev < bottom_limit)

            return 0;

        rev = rev * 10 + x % 10;

        x /= 10;
    }
    return rev;
}

};

Upvotes: 1

Valerij Dobler
Valerij Dobler

Reputation: 2764

The approach you've chosen is not that far off.

  1. You currently check the input x to be in range of unsigned integer. But they ask to check x-reversed instead.
  2. You aggregate your answer in an integer, hence you might overflow unnoticed.

Both of your problems can be solved if you aggregate your result num in an variable of type long instead and reject/zero the answer if after reversing it is out of bounds of unsigned int.

Alternative you can use Math.addExact(a, b), Math.multiplyExact(a,b) and a try-catch to exit immediately upon overflow.

Upvotes: 1

Related Questions