Reverse Integer - Bit Manipulation - Leetcode 7 - Python

0:00 - Read the problem
5:07 - Drawing Explanation
9:05 - Coding Explanation

leetcode 7

#bit #manipulation #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[Ynno]

Crazy how like 90% of the most upvoted Python solutions on this problem didn't understand or just ignored the constraint on staying within 32 bits.

[bhaskyOld]

Great explanation. Just a question, in case of "res == MAX//10", the digit needs to be grater than 7 to overflow, not grater than equal.

[infiniteloop]

Just finished this problem as the final problem of the NeetCode 150! Neetcode ALL TIME!

[gitarowydominik]

This solution clearly has nothing to do with BIT MANIPULATION. :)

[arpitagarwal]

Instead of `digit >= MAX%10` and `digit <= MIN%10`, Shouldn't it be `digit > MAX%10` and `digit < MIN%10` ?

[romelpascua]

I searched if you had solved this question just last night. You read my mind!

[John-yesj]

one can also check for overflow:
a + b > INT_MAX <=> a > INT_MAX - b (it will overflow)
or underflow:
assume a < 0
a + b < INT_MIN <=> b < INT_MIN - a (it will underflow; INT_MIN - a is safe, because a is negative and the operation will be a sum in the end)

[untrall]

I think MIN should also use int(math.fmod(MIN, 10)) and int(MIN / 10)

[yuvrajparmar]

finally a correct solution I was looking for. Thanks for the explanation.

[praveendantam]

Here you mentioned bit manipulation, but it seems you didn't used bit manipulation.

Can we do this problem using bit manipulation?

Anyone please clarify this to me.

Thanks in advance!

[craignemeth]

Why is this under bit manipulation on neetcode? I was going insane trying to figure out some cool bit manipulation method that must exist when I could clearly see it was a problem to be solved in base 10 not base 2...

[Raphael-bqfc]

I think this guy's solutions are the best

[ssiddique_info]

MIN is a negative number, why MIN % 10 will work fine but % will not work for a negative number in line 11?

[alexm]

There are unneeded checks in your overflow logic. You only really have to check if((ret > INT_MAX / 10) || (ret < INT_MIN / 10)). The reason being is that an input such as your example's 81463847412 is not possible since the input parameter is a 32 bit integer. I did this problem in C++ and I was originally just going to detect overflows after the operation but leetcode just throws an exception. I'm not sure if python allows 64 bit integers as an input parameter since it's not a typed language, but for C++ trying an input value that doesn't fit a 32 bit integer will not allow the code to run.

[applepaul]

why do we need to check
(res > INT_MAX/10 || (res == INT_MAX/10 && digit > INT_MAX%10))
*based on the input size* : between -2^31 to 2^31 - 1, *we can never have the first digit (from left) of any input to be greater than 2*.

So when we reverse this number, the units place (first from right) can never have any number greater than 2. This condition gets *set by default due to the constraints on input*

So even if we remove this piece from the code, it should run fine

[AlexN]

This is suboptimal, since you dp a division - a slow operation - on every iteration of the loop. Instead, as you reconstruct your reversed number low-to-high, it's only the highest power of 10 that can overflow the result. So you can go 10^(0->8) without checks, and then just do two checks - two divisions - before adding the final 10^9. Suppose i==0 and ten_power==10^9

if(INT_MIN / ten_power > digits[i]) {
return 0; // can we even multiply this number by 10^9?
}
if(result < INT_MIN - digits[i] * ten_power) {
return 0; // will it overflow if we add it to our result?
}
result += digits[i] * ten_power; // result is always negative

[thankmelater]

I have the simplest solution without worrying about the overflows.

Make a simple reverse method. int reverse = getReverse(x);
Then, find reverse of reverse, int reverseOfReverse = getReverse(reverse)
Check if reverserOfReverse and x are same (after removing trailing zeros from x, like for 120, and 21 case)
If both are same then return reverse
Else some overflow had occurred during reversal, and return 0

[jiteshsharma]

Can someone confirm the Time complexity?
I think it will be O(1) because loop will always run 10 time due to our overflow condition.
or it will O(x) where x is number of digits?

[ekoyanachi]

Thanks for solving the problem. Can you provide detail on where bit manipulatin is used while reversing integer?

[huberttiddlywinks]

You don't need to check any conditions inside the loop because you'll only go outside the range once you hit the last iteration. Simply reverse the input normally and check if res < INT_MIN || res > INT_MAX before returning. Remember that the input is constrained to -2^31 <= x <= 2^31-1.

This way you're trading off 9 extra if checks for possibly 1 extra iteration which is better for performance since branching is slower than Math ops.