Reverse 32bit integer

Question

I'm trying to solve an exercie in leetcode.com which deals with signed 32bit integers.

The task is:

Return the inverse of a signed 32bit integer and return 0 if it overflows the 32bit signed integer's range.

In Wikipedia:

A 32-bit register can store 32 different values. The range of integer values that can be stored in 32 bits depends on the integer representation used. With the two most common representations, the range is 0 through 4,294,967,295 (2^32 − 1) for representation as an (unsigned) binary number, and −2,147,483,648 (−2^31) through 2,147,483,647 (2^31 − 1) for representation as two's complement.

So, if what i understood is correct i should test between the intervals 0 to (2^31)-1 and (-2^31) to 0 otherwise, return 0.

Here is my code:

def reverse_int(nums):
    a = str(nums)

    if 0 < nums <= (1 << 31)-1:
        return int(a[::-1])

    elif (-1 << 31) <= nums < 0:
        return -(int(a[:-len(a):-1]))
    else:
        return 0

Here is my problem: When i test my code on the website with:

nums = 1534236469 # Fail
nums = 1463847412 # Success
nums = 9000000    # Success

Why my current code fails with 1534236469 ? isn't 1534236469 in the range of 32 bit signed integers ? What i'm missing ?

Solution 1

As mentioned in the comments you must first reverse and then check. However here's a different way of checking.

To check you can just & the result with the appropriate mask.

So in your case the limits are −2,147,483,648 and 2,147,483,647 the hex values of them are -0x80000000 and 0x7fffffff

Try this in the interpreter.

>>> 0x7fffffff
2147483647
>>> 2147483647 & 0x7fffffff   #within limit
2147483647

Values exceeding the limit, you can see some other value is displayed.

>>> 2147483648 & 0x7fffffff     #Exceeds limit
0
>>> 98989898989898 & 0x7fffffff  #Exceeds limit
1640235338

But when the value is within limit. The value is given as output.

>>> 1 & 0x7fffffff               #within limit
1
>>> 780 & 0x7fffffff
780

For negative values

 >>> -0x80000000     #Limit
-2147483648
>>> -2147483648 & -0x80000000
-2147483648

When the value is within the range. The limit is given as output.

>>> -2147483647 & -0x80000000
-2147483648
>>> -2 & -0x80000000          #within limit
-2147483648
>>> -2323 & -0x80000000
-2147483648

However if value is out of range you can see some other value is displayed.

>>> -2147483649 & -0x80000000
-4294967296
>>> -999999999999 & -0x80000000
-1000727379968

You can make use of this well and good to get what you want!

Here is a program that does what you want.

def reverse(x):
    str_x = str(x)
    if x<0:
        str_x = '-'+str_x[::-1][:-1]
        x = int(str_x)
    else:
        str_x = str_x[::-1]
        x = int(str_x)
    neg_limit= -0x80000000
    pos_limit= 0x7fffffff

    if(x<0):
        val=x&neg_limit
        if(val==neg_limit):
            return x
        else:
            return 0
    elif(x==0):
        return x
    else:
        val = x&pos_limit
        if(val==x):
            return x
        else:
            return 0

value = int(input("Enter value: "))
print(reverse(value))

The part below just reverses for both negative and positive values.

if x<0:
    str_x = '-'+str_x[::-1][:-1]
    x = int(str_x)
    print(x)
else:
    str_x = str_x[::-1]
    x = int(str_x)
    print(x)

Set the limits neg_limit= -0x80000000 and pos_limit= 0x7fffffff and check for them according to the explained logic.

Solution 2

The solution is already there, I am posting this because this might be helpful for newbies like me. I used the void's solution (above) to make it complete. At first, I did the testing without performing the reverse method, it was showing the problem as mentioned in the original question. Then I did the test after reversing the numbers in both positive and negative case and it worked.

def reverse(self, x: int) -> int:
        neg_limit =-0x80000000 # hex(-2**31-1),see details in accepted answer above
        pos_limit = 0x7fffffff #hex(2**31-1)
        if x >0:
            reverse_num = int(str(x)[::-1])
            if reverse_num & pos_limit==reverse_num: #conditions explained above
                return reverse_num
            else:
                return 0

        elif x <0:
            reverse_num = -int(str(abs(x))[::-1])
            if reverse_num&neg_limit == neg_limit:
                return reverse_num
            else:
                    return 0
        else:
            return 0

Solution 3

This happen because nums = 1534236469 is in the range of 32 bit signed integer, but it's reverse 9646324351 is not in the range of 32 bit signed integer.

class Solution:
def reverse(self, x: int) -> int:
    if x in range((-1 << 31),(1 << 31)-1):
        r=0
        c=False
        if(x<0):
            c=True
            x*=-1

        while(x!=0):
            r=10*r+x%10
            x=x//10
        if(c):
            r*=-1
        if r in range((-1 << 31),(1 << 31)-1):
            return r
        else:
            return 0
    else:
        return 0

Solution 4

Simple and pure mathematical -

def reverse(self, x: int) -> int:
        r = 2 ** 31
        maxLimit = r - 1
        minLimit = r * -1
        rev = None
        negative = False

        if x < 0:
            negative = True
            x = x * -1

        while True:
            mod = x % 10
            x = (x - mod) / 10

            if not rev:
                rev = mod
            else:
                rev = (rev * 10) + mod

            if x <= 0:
                break

        if negative:
            rev = rev * -1

        returnValue = int(rev)
        if returnValue < minLimit or returnValue > maxLimit:
            return 0 #Return whatever you want. if overflows
        return int(rev)

Solution 5

Simple, mathematical and pythonic way based on @Keshari's solution

def reverse(x):
    is_neg = x < 0
    imax = (1 << 31) - 1
    imin = (-1 << 31)
    r = 0
    x = abs(x)
    while x:
        x, m = divmod(x, 10)
        if (r > imax / 10) or (r == imax / 10 and m > 7):
            return 0
        if (r < imin / 10) or (r == imin / 10 and m < -8):
            return 0
        r = (r * 10) + m
    return r * -1 if is_neg else r

View more solutions

Comments

[Chiheb Nexus]

Or, in a much simpler way compare the reversed int of str_x if it's between (-1 << 31) and (1 << 31)-1. If not return 0. By the way your approach is correct too, but too verbose.

[void]

Yes it is but wanted to mention the use of & and using a mask

[kafran]

Nice mathematical way to think. I rewrote this in a more pythonic way. The statement rev * 10 + mod can cause overflow.