15

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 ?

8
  • What output do you get for the case that fails?
    – Zeokav
    Jun 16, 2017 at 5:33
  • For example, for 1534236469 on the website it should return 0. This means that 1534236469 overflows the range of 32 bit signed integers. Jun 16, 2017 at 5:34
  • 1
    But it doesn't overflow.
    – Zeokav
    Jun 16, 2017 at 5:35
  • In wikipedia they said the two most common representations. There is other representations of 32bit integers ? Jun 16, 2017 at 5:37
  • 6
    You need to reverse then check if it overflows. Jun 16, 2017 at 5:38

7 Answers 7

29

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.

2
  • 2
    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. Jun 16, 2017 at 7:20
  • 4
    Yes it is but wanted to mention the use of & and using a mask
    – void
    Jun 16, 2017 at 7:28
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
1

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
1

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)
1
  • Nice mathematical way to think. I rewrote this in a more pythonic way. The statement rev * 10 + mod can cause overflow.
    – kafran
    Aug 26, 2020 at 3:23
1

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
0

Another way of checking the overflow of the result without using any additional variables for limits is this:

def reverse(x):
    num = str(abs(x))

    if x < 0:
        result = -1 * int(num[::-1])
    else:
        result = int(num[::-1])

    if result not in range((-1 << 31), (1 << 31) - 1):
        return 0

    return result
0

Reverse signed integer, but return 0 if outside int32 limits given as below 2^31 or above 2^31 -1.

[Embedding it in the solution class is part the problem site requirement.]

I am new to Python so please criticize -- in fact this is my first Python function and first 'class'.

It seems easy and clear to do the following:

class Solution:
    def reverse(self, x: int) -> int:
        s = str(abs(x))[::-1]
        sign = -1 if x < 0 else 1
        rx = int(s) * sign
        return 0 if rx < -2**31 or rx > 2**31 - 1 else rx

Collapsing out the temporary values s, rx, and/or sign is easy too but doesn't makes is less clear.

Seriously I'd appreciate criticism as this is literally my first Python; been meaning to learn it for years.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.