we will reach this digit condition in only one case ie given x is 1463847412 so its reverse would be 2147483641 which is less than 2147483648 hence it is possible. but this is the only case of 214748364 getting equal to INT_MAX/10 ie 2147483648 and hence only we return the reverse of it and NOT 0; so just check if rev>INT_MAX/10 or rev
I prefer hard coding MAX_LAST_DIGIT=7 and MIN_LAST_DIGIT=8 -- no need to do math every iteration, it makes the code more readable and performant at the same time.
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
Well, that's not really a solution -- it's more of a hack. And it depends on the platform it is being run on, and is a total misuse of error handling. It won't work if the underlying VM or system can actually handle a 64 bit integer, and nobody ever wants code that relies on exception handling to get a result in a real production situation. It's pretty much a B-line toward putting your resume in the trash bin for the interviewer.
@@BitsandAtoms If it can handle a 64 bit integer, why aren't we using one in the solution itself? And why is this considered an exception? These boundary conditions is expected behavior, otherwise it would actually throw an exception right? Also aren't these leetcode questions meant for you to solve a problem within specific confines? And why are you not allowed to assume that the behavior of x language is the expected behavior?
@@romo119 You are allowed to do it and it will work. It's garbage coding practice though and if you want to get a job as a programmer you need to write good, maintainable code that doesn't use lazy hacks.
import math class Solution: def reverse(self, x: int) -> int: MIN = -2 ** 31 MAX = 2 ** 31 - 1 res = 0 while x != 0: digit = int(math.fmod(x, 10)) x = int(x / 10) if ( res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10) ): return 0 if ( res < int(MIN / 10) or (res == int(MIN / 10) and digit < math.fmod(MIN, 10)) ): return 0 res = (res * 10) + digit return res
Another way to do it def reverse(x): res = 0 if x < 0: symbol = -1 x = -x else: symbol = 1 while x: popped = x % 10 res = res * 10 + popped x //= 10 return 0 if res > 2**31 else res*symbol
Defeats the whole purpose-- you're assuming that res is represented correctly as a 64-bit integer, but the problem clearly states that we are not allowed to do this.
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
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
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.
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!
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...
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)
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
You have to read the problem carefully. This would work in Python but not, say, C. It would overflow and never be less than or greater than INT_MIN or INT_MAX. These checks are required to ensure the number will fit before performing the assignment. If it does not fit then you must return there. If you did not do this, in many programming languages it would simply give you the wrong answer.
thanks for the sharing, that is so good. but I am wondering the two "if " condition may be "if res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10):" and "if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):" it should be less or greater not less or equal or greater or equal, cause the condition the problem give me does include 2^31 - 1 and -2^31. However, the intheresting thing is both solution can pass.
You don't need to check the condition res==MAX//10 && digit>=MAX%10 cause this would mean that the input should be 7463847412 ( reverse of 2147483647). This is outside the int range as in the question they mentioned the input is an integer. Similarly you also can avoid the res==MIN//10 && digit
or you can simply convert from int to string, reverse it with [::-1], in case if there is a "-" character, just remove it at first and add "-" again before reversing the string. And then reconvert to int, it's much faster
Except it breaks the rules of the problem. You can't do this within 32-bits. 1000000009 reversed would be 9000000001, which has a 35-bit signed integer representation. Leetcode won't reject it because they don't verify the internal state of your code, but you wouldn't be able to cheat like that with a real human. Honestly, any solution which uses a conversion to string I'd expect to be rejected by the interviewer. If you aren't allowed to use a 64-bit integer, using a 80-bit string (for a ten digit input) doesn't seem like it would be acceptable.
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?
class Solution: def reverse(self, x: int) -> int: rev_x = int("-"+str(x)[::-1][:-1]) if x= 32 else rev_x This is how I solved it... I hope this method is not frowned upon. It seems weirdly short
because you do the reversing in your code then u check if it is within a range, in this exercice the idea is that your memory can't handle it so you should stop the code and return 0 if you overflow
For guys struggling with Java, there is a simple way to determine integer overflow. You can directly store a temporary reverse result. If the reverse result divided by 10 does not equal the previous result, there is an overflow. The complete code is provided below: public int reverse(int x) { int res = 0; while (x != 0) { int temp = res * 10 + x % 10; if (temp / 10 != res) { // overflow return 0; } res = temp; x /= 10; } return res; }
At 10:30 the operations are correct according to Mathematics. In math, A=Q*B+M which is exactly it is giving. Other languages use the result of division algorithm which is anticipated in here but mathematically this behaviour seems appropriate.
yo thanks man , the course i followed has years ago solution , at that time it was in easy problem , now its medium , they had not added the constrainst prolly
class Solution { public int reverse(int x) { long res = 0; while(x!=0){ res = res * 10 + x%10; x = x/10; } if(res < Integer.MIN_VALUE || res > Integer.MAX_VALUE){ return 0; }else{ return (int) res; } } }
this is my solution, i only use part of neetcode solution for the outbound cases: class Solution: #half mine, half neetcode solution def reverse(self, x: int) -> int: negative = x < 0 x = abs(x) MIN = -2147483648 MAX = 2147483647 res = 0 while x > 0: lastdigit = x % 10 x = int(x/10)
#part from neetcode solution if(res > MAX // 10 or (res == MAX // 10 and lastdigit >= MAX % 10 )): return 0 if(res < MIN // 10 or (res == MIN // 10 and lastdigit
``` if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10): ``` `digit < MIN % 10` seems like *almost* bug since you're using regular % on the negative MIN, which will give a positive number (in this case `2`), whereas `digit` will always be zero or negative on this code path. However, It's not technically a bug because it's unreachable code. There's no case where `res == MIN // 10` is True where the digit will be invalid, so the condition will always be short-circuited. `digit < MIN % 10` could just be removed.
Please solve leetcode problem 493. Reverse Pairs. I've been stuck on it since morning. Cannot seem to find any breakthrough. In this question, the Java and C approach when applied using python yields TLE.
The above code return 0 ans for negative numbers. Following is the corrected code.. def reverse(self, x): MIN = -2147483648 MAX = 2147483647 is_negative = x < 0 x = abs(x)
res = 0 while x: digit = x % 10 x //= 10 if res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10): return 0 if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10): return 0 res = (res * 10) + digit return -res if is_negative else res
I have just one doubt, if for reversing the number which is a negative integer you're using fmod to hold last value of the integer then how come in the second if statement you're not using fmod to get hold of the last value of min value. This is also true with floor division operator
because that hack is only used for negative numbers. Since MIN is a constant number, MIN % 10 is 8. He could've just put 8 tbh, but it doesn't matter. Same for MAX % 10, it's 7. You can put 7 there and it will still work
class Solution: def reverse(self, x: int) -> int: y = x< 0 x = abs(x) revs = 0 MIN = -2147483648 MAX = 2147483647 while x > 0: rem = x%10 revs = revs*10 + rem x =x//10 if MIN
@@hemesh5663 6:26 " how could we detect that this integer overflows without actually calculating it". Your code allows revs to calculate a value that overflows, i.e. a value outside of the specified range.
Shouldn't the condition be: if(ans > Integer.MAX_VALUE/10 || (ans == Integer.MAX_VALUE/10 && d > Integer.MAX_VALUE%10)) return 0; if(ans < Integer.MIN_VALUE/10 || (ans == Integer.MIN_VALUE/10 && d < Integer.MIN_VALUE%10)) return 0; The last digit can be equal but not greater?
I don't know if it's just me, but this looks more complicated than it needs to be 😅 I would just treat both negative and positive cases with the same code and put all conditions into one if statement, like this: ``` class Solution: def reverse(self, x: int) -> int: negative = x < 0 x = x if not negative else (-1) * x limit = 2**31 - 1 if not negative else 2**31 res = 0 while x != 0: if res > (limit - x % 10) // 10: return 0 res = res * 10 + x % 10 x //= 10 return res if not negative else (-1) * res ```
Apparently this is a "hack" according to "Pasquale Ranalli" and "Bits and Atoms" in above comment. I don't think it's a hack at all and I would accept this solution as an interviewer
That would work, but the question stipulates that 64-bit integers are not supported. If your res > INT_MAX or res < INT_MIN, it means res no longer fits in a 32 bit integer, so that's not allowed.
Is it against the rules to turn x into a string or something? Because all I did was convert x into a string, reverse it, and convert it back into an integer. Then check if it's within the -2^31 2^31 range. Made it the easiest leetcode problem I've solved.
> Because all I did was convert x into a string, reverse it, and convert it back into an integer. This requires up to 35 bits for the signed integer representation. If the input is -1000000009, then you are storing the integer -9000000001. That's 10111100111100011101110010111111111 in 2's complement signed representation. You can just count the bits. Positive 9000000001 also requires 35-bits, but it's a bit less obvious from just looking at it because it has a leading zero as the sign bit. It's debatable whether you should use a string (I'd personally say no), but I think it's pretty clear you can't use an integer greater than 32 bits. You ignored the constraints in the description which due to limitations of the Leetcode runtime environment it can't enforce.
I think if once you converted it back into an integer and it happened to be outside the range, it's already against the rules. The goal is to never allow any integer (not just the result) to get outside that range in the first place, at least that's my understanding
The following is a much easier way, please have a look: def reverse(self, x: int) -> int: upper_limit = (2**31) - 1 lower_limit = (-2**31) if x > 0: x = str(x) x = x[::-1] x = int(x) if x in range(lower_limit, upper_limit): return x else: return 0
elif x < 0: x = str(x) x1 = x[0] x = x.replace("-","") x = x[::-1] x1 += x x1 = int(x1) if x1 in range(lower_limit, upper_limit): return x1 else: return 0
Anyone can do this with a string implementation. Companies want to know how you are going to manipulate a number using bit manipulation techniques, not strings
The explanation offered in the video is not that great, this is a math problem and he is coming up with raucous ways to just add more overflow detection logic than is required. Please, don't over-engineer the solution as it makes it difficult to understand.
Because the problem description says: Assume the environment does not allow you to store 64-bit integers (signed or unsigned). I.e. only use 32-bit integers or smaller. MAX is literally the maximum value you can store in a 32-bit signed integer, it's impossible that any signed 32-bit could be greater than it. If you have a number that is bigger that it, you already broke the rules.
I have implemented a different solution which for me was simpler to code and understand. I was simply undoing the last operation and checking if it gives me my previous result. for example if before reversing my last digit the result so far was 96463243, and the last digit to add was a 0 I would say: if (96463243*10/10 == 96463243) return 0; If after multiplying by 10 an overflow happens (which does in the example above) the entire integer will be different
if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10): Why did you use // 10 and % 10 instead of fmod and int(/) trick? cos MIN % 10 would give you positive number. Let's say x = -2147483649 (below MIN) x % 10 would be 1 instead of -9 and MIN % 10 would be 3 instead of -7 OK + 10 still gives you the same inequalities.
isn't the check MIN outbound condition wrong? as MIN //10=-214748365, so with the video code never check if -214748364+last digit outbound. good method & explain tho.
Python's mod operation (a % b) behaves like a clock of size b. So, if you do 11 % 10 you get 1, but if you do -1 % 10 you get 9, because you wrapped around from 0 to the largest value in [0, 9]. This is useful for traversing a circular array counter-clockwise, for example, but can cause some unexpected behavior, like in this problem. The fmod function behaves like you might expect, math.fmod(-1, 10) == -1.0. It returns a float so that's why NC casted it to int.
Save yourself some time 1. This code does NOT work on LeetCode 2. There is no need to check if res == MAX // 10 for overflow, this case is covered by input itself.
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.
This solution clearly has nothing to do with BIT MANIPULATION. :)
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.
I think you're right.
Just finished this problem as the final problem of the NeetCode 150! Neetcode ALL TIME!
Instead of `digit >= MAX%10` and `digit
Those conditions can just be deleted, it's unreachable code.
we will reach this digit condition in only one case ie given x is 1463847412
so its reverse would be 2147483641 which is less than 2147483648 hence it is possible. but this is the only case of
214748364 getting equal to INT_MAX/10 ie 2147483648 and hence only we return the reverse of it and NOT 0;
so just check if rev>INT_MAX/10 or rev
I prefer hard coding MAX_LAST_DIGIT=7 and MIN_LAST_DIGIT=8 -- no need to do math every iteration, it makes the code more readable and performant at the same time.
I think MIN should also use int(math.fmod(MIN, 10)) and int(MIN / 10)
Yep
I searched if you had solved this question just last night. You read my mind!
our guy is getting more popular :)
🤓
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
Well, that's not really a solution -- it's more of a hack. And it depends on the platform it is being run on, and is a total misuse of error handling. It won't work if the underlying VM or system can actually handle a 64 bit integer, and nobody ever wants code that relies on exception handling to get a result in a real production situation.
It's pretty much a B-line toward putting your resume in the trash bin for the interviewer.
@@BitsandAtoms If it can handle a 64 bit integer, why aren't we using one in the solution itself? And why is this considered an exception? These boundary conditions is expected behavior, otherwise it would actually throw an exception right? Also aren't these leetcode questions meant for you to solve a problem within specific confines? And why are you not allowed to assume that the behavior of x language is the expected behavior?
@@romo119 You are allowed to do it and it will work. It's garbage coding practice though and if you want to get a job as a programmer you need to write good, maintainable code that doesn't use lazy hacks.
MIN is a negative number, why MIN % 10 will work fine but % will not work for a negative number in line 11?
looks like an oversight, it won't work.
import math
class Solution:
def reverse(self, x: int) -> int:
MIN = -2 ** 31
MAX = 2 ** 31 - 1
res = 0
while x != 0:
digit = int(math.fmod(x, 10))
x = int(x / 10)
if (
res > MAX // 10 or
(res == MAX // 10 and digit > MAX % 10)
):
return 0
if (
res < int(MIN / 10) or
(res == int(MIN / 10) and digit < math.fmod(MIN, 10))
):
return 0
res = (res * 10) + digit
return res
Another way to do it
def reverse(x):
res = 0
if x < 0:
symbol = -1
x = -x
else:
symbol = 1
while x:
popped = x % 10
res = res * 10 + popped
x //= 10
return 0 if res > 2**31 else res*symbol
Defeats the whole purpose-- you're assuming that res is represented correctly as a 64-bit integer, but the problem clearly states that we are not allowed to do this.
mate ,your code is way better than those in the video
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
If input is 2**31 - 1 aka 2147483647 then the reverse number would start from 7 which exceeds the max allowed value.
finally a correct solution I was looking for. Thanks for the explanation.
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
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.
Yes, I agree with you. This input is impossile.
[1-7]463847412 is a valid input and will fail if we only check second to last bit
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!
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...
Right! Kept me scratching my head!
us
In an edge case, the last digit can not be greater than 2 because x is also a 32-bit signed integer. digit >= Max % 10 and digit
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)
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
You have to read the problem carefully. This would work in Python but not, say, C. It would overflow and never be less than or greater than INT_MIN or INT_MAX. These checks are required to ensure the number will fit before performing the assignment. If it does not fit then you must return there. If you did not do this, in many programming languages it would simply give you the wrong answer.
I think this guy's solutions are the best
thanks for the sharing, that is so good. but I am wondering the two "if " condition may be "if res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10):" and "if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):" it should be less or greater not less or equal or greater or equal, cause the condition the problem give me does include 2^31 - 1 and -2^31. However, the intheresting thing is both solution can pass.
even if digit>1 it will pass, because in order that res==max% 10, the input must be i463847412 and i can't be greater than 1
Thanks for solving the problem. Can you provide detail on where bit manipulatin is used while reversing integer?
You don't need to check the condition res==MAX//10 && digit>=MAX%10 cause this would mean that the input should be 7463847412 ( reverse of 2147483647). This is outside the int range as in the question they mentioned the input is an integer. Similarly you also can avoid the res==MIN//10 && digit
@Neetcode - I think the second part of the if conditions should be using on greater than and less than checks, rather than what you have >= , MAX % 10
Because if the reversed digit is equal to MAX , it is not considered overflow or if negative number is equal to MIN , it is not underflow
or you can simply convert from int to string, reverse it with [::-1], in case if there is a "-" character, just remove it at first and add "-" again before reversing the string. And then reconvert to int, it's much faster
But the space complexity will be huge
Except it breaks the rules of the problem. You can't do this within 32-bits. 1000000009 reversed would be 9000000001, which has a 35-bit signed integer representation. Leetcode won't reject it because they don't verify the internal state of your code, but you wouldn't be able to cheat like that with a real human.
Honestly, any solution which uses a conversion to string I'd expect to be rejected by the interviewer. If you aren't allowed to use a 64-bit integer, using a 80-bit string (for a ten digit input) doesn't seem like it would be acceptable.
sorter
def reverse(self, x: int) -> int:
s = abs(x)
rs = 0
while s:
temp = s % 10
s = s//10
if rs > math.pow(2,31) // 10:
return 0
break
rs = rs*10 + temp
return rs if x>0 else -rs
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
min =-2147483648;
max = 2147483647;
res = 0;
while x:
digit = int(math.fmod(x,10));
x=int(x/10);
if (res > max//10 or (res == max//10 and digit >= max % 10)):
return 0;
if(res < min//10 or (res == min//10 and digit
Run on python3
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?
class Solution:
def reverse(self, x: int) -> int:
rev_x = int("-"+str(x)[::-1][:-1]) if x= 32 else rev_x
This is how I solved it... I hope this method is not frowned upon. It seems weirdly short
This beats 96% on both memory and time
because you do the reversing in your code then u check if it is within a range, in this exercice the idea is that your memory can't handle it so you should stop the code and return 0 if you overflow
Check if negative, convert to string, reverse digits, convert back to number
LeetCode problem 7 Reverse Integer - difficulty is now Medium
That's good, it's definitely not easy
For guys struggling with Java, there is a simple way to determine integer overflow. You can directly store a temporary reverse result. If the reverse result divided by 10 does not equal the previous result, there is an overflow. The complete code is provided below:
public int reverse(int x) {
int res = 0;
while (x != 0) {
int temp = res * 10 + x % 10;
if (temp / 10 != res) { // overflow
return 0;
}
res = temp;
x /= 10;
}
return res;
}
At 10:30 the operations are correct according to Mathematics. In math, A=Q*B+M which is exactly it is giving. Other languages use the result of division algorithm which is anticipated in here but mathematically this behaviour seems appropriate.
where 0
yo thanks man , the course i followed has years ago solution , at that time it was in easy problem , now its medium , they had not added the constrainst prolly
class Solution {
public int reverse(int x) {
long res = 0;
while(x!=0){
res = res * 10 + x%10;
x = x/10;
}
if(res < Integer.MIN_VALUE || res > Integer.MAX_VALUE){
return 0;
}else{
return (int) res;
}
}
}
we cannot use long
class Solution:
def reverse(self, x: int) -> int:
if x > 0: # handle positive numbers
a = int(str(x)[::-1])
if x
Clear explanation for integer overflow !
Thx !
this is my solution, i only use part of neetcode solution for the outbound cases:
class Solution:
#half mine, half neetcode solution
def reverse(self, x: int) -> int:
negative = x < 0
x = abs(x)
MIN = -2147483648
MAX = 2147483647
res = 0
while x > 0:
lastdigit = x % 10
x = int(x/10)
#part from neetcode solution
if(res > MAX // 10 or
(res == MAX // 10 and lastdigit >= MAX % 10 )):
return 0
if(res < MIN // 10 or
(res == MIN // 10 and lastdigit
```
if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):
```
`digit < MIN % 10` seems like *almost* bug since you're using regular % on the negative MIN, which will give a positive number (in this case `2`), whereas `digit` will always be zero or negative on this code path. However, It's not technically a bug because it's unreachable code. There's no case where `res == MIN // 10` is True where the digit will be invalid, so the condition will always be short-circuited. `digit < MIN % 10` could just be removed.
Please solve leetcode problem 493. Reverse Pairs. I've been stuck on it since morning. Cannot seem to find any breakthrough. In this question, the Java and C approach when applied using python yields TLE.
The above code return 0 ans for negative numbers. Following is the corrected code..
def reverse(self, x):
MIN = -2147483648
MAX = 2147483647
is_negative = x < 0
x = abs(x)
res = 0
while x:
digit = x % 10
x //= 10
if res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10):
return 0
if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):
return 0
res = (res * 10) + digit
return -res if is_negative else res
Use return res if abs(res) < 0x80000000 else 0
or you can use return res if abs(res)
I have just one doubt, if for reversing the number which is a negative integer you're using fmod to hold last value of the integer then how come in the second if statement you're not using fmod to get hold of the last value of min value. This is also true with floor division operator
can you make more videos on bit manipulation XOR such as missing number (268) please
Thanks for the great explanation. But why are the "hacks" used in lines 11 & 12 of the code (for dumb python 🙂) not used in lines 14 - 18?
Exactly
Did u find the same problem ?
@@Saurabhsingh-cl7px Yeah, I guess it was an oversight on his part.
because that hack is only used for negative numbers.
Since MIN is a constant number, MIN % 10 is 8. He could've just put 8 tbh, but it doesn't matter.
Same for MAX % 10, it's 7. You can put 7 there and it will still work
@@anonymoustv8604 What do you mean? MIN *is* a negative number.
simpler logic, for x > 0, pop = x % 10,
if ( rev > (INT_MAX - pop)//10 ) :
return 0;
class Solution:
def reverse(self, x: int) -> int:
y = x< 0
x = abs(x)
revs = 0
MIN = -2147483648
MAX = 2147483647
while x > 0:
rem = x%10
revs = revs*10 + rem
x =x//10
if MIN
Yes this is very good since you use O(1) memory. In some ways i prefer this solution to mine in the video.
@@NeetCode I have a doubt
in interview shd I focus on time or space complexity as there is trade off
The problem with this solution is that variable "revs" will store an integer outside of the range [-2^31, 2^31 - 1]
@@christianp3388 I have checked it using that if condition whether revs is between my min and max
@@hemesh5663 6:26 " how could we detect that this integer overflows without actually calculating it". Your code allows revs to calculate a value that overflows, i.e. a value outside of the specified range.
Shouldn't the condition be:
if(ans > Integer.MAX_VALUE/10 || (ans == Integer.MAX_VALUE/10 && d > Integer.MAX_VALUE%10)) return 0;
if(ans < Integer.MIN_VALUE/10 || (ans == Integer.MIN_VALUE/10 && d < Integer.MIN_VALUE%10)) return 0;
The last digit can be equal but not greater?
I found this a really helpful explanation.
If Reverse is not able to fit in 32-bit. How come Input fit in 32-bit integer?
I don't know if it's just me, but this looks more complicated than it needs to be 😅
I would just treat both negative and positive cases with the same code and put all conditions into one if statement, like this:
```
class Solution:
def reverse(self, x: int) -> int:
negative = x < 0
x = x if not negative else (-1) * x
limit = 2**31 - 1 if not negative else 2**31
res = 0
while x != 0:
if res > (limit - x % 10) // 10:
return 0
res = res * 10 + x % 10
x //= 10
return res if not negative else (-1) * res
```
Apparently this is a "hack" according to "Pasquale Ranalli" and "Bits and Atoms" in above comment. I don't think it's a hack at all and I would accept this solution as an interviewer
Won't your solution fail immediately on this line:
x = x if not negative else (-1) * x
When your input is -2^31, x will overflow.
Quick question: why cant you just check if res < INT_MIN or res > INT_MAX? Thank you for the video.
That would work, but the question stipulates that 64-bit integers are not supported.
If your res > INT_MAX or res < INT_MIN, it means res no longer fits in a 32 bit integer, so that's not allowed.
NICE SUPER EXCELLENT MOTIVATED
great explanation. thanks for all the efforts
Is it against the rules to turn x into a string or something? Because all I did was convert x into a string, reverse it, and convert it back into an integer. Then check if it's within the -2^31 2^31 range. Made it the easiest leetcode problem I've solved.
> Because all I did was convert x into a string, reverse it, and convert it back into an integer.
This requires up to 35 bits for the signed integer representation. If the input is -1000000009, then you are storing the integer -9000000001. That's 10111100111100011101110010111111111 in 2's complement signed representation. You can just count the bits. Positive 9000000001 also requires 35-bits, but it's a bit less obvious from just looking at it because it has a leading zero as the sign bit. It's debatable whether you should use a string (I'd personally say no), but I think it's pretty clear you can't use an integer greater than 32 bits.
You ignored the constraints in the description which due to limitations of the Leetcode runtime environment it can't enforce.
I think if once you converted it back into an integer and it happened to be outside the range, it's already against the rules. The goal is to never allow any integer (not just the result) to get outside that range in the first place, at least that's my understanding
They've updated this to be a medium problem now in leetcode
Thanks for the wonderful explanation!
div in python of negative numbers is giving different answer(not python3**)
Java Code:
class Solution {
public int reverse(int x) {
StringBuilder s = new StringBuilder();
s.append(x);
char sign = '+';
if(s.charAt(0) == '-')
{
sign = s.charAt(0);
s.delete(0,1);
}
s.reverse();
long val = Long.parseLong(s.toString());
if(val > Integer.MAX_VALUE || val < Integer.MIN_VALUE)
return 0;
if(sign == '-')
return -1 * (int) val;
return (int) val;
}
}
Can we use result%mod where mod= pow(2, 31) -1 if the result value has decreased from its previous value we can return 0 ?
The following is a much easier way, please have a look:
def reverse(self, x: int) -> int:
upper_limit = (2**31) - 1
lower_limit = (-2**31)
if x > 0:
x = str(x)
x = x[::-1]
x = int(x)
if x in range(lower_limit, upper_limit):
return x
else:
return 0
elif x < 0:
x = str(x)
x1 = x[0]
x = x.replace("-","")
x = x[::-1]
x1 += x
x1 = int(x1)
if x1 in range(lower_limit, upper_limit):
return x1
else:
return 0
else:
return 0
Anyone can do this with a string implementation. Companies want to know how you are going to manipulate a number using bit manipulation techniques, not strings
Python still acts wonky with int(x/10). In my case it's still rounding down to the lowest number. In the case of -123, it's return -13.
returning -12 when i just tested in for python3
The explanation offered in the video is not that great, this is a math problem and he is coming up with raucous ways to just add more overflow detection logic than is required. Please, don't over-engineer the solution as it makes it difficult to understand.
Can't understand why we are using two different ways of mod:
int(math.fmod(x, 10))
MIN_INT % 10
It's a mistake, but `MIN_INT % 10` is actually never evaluated. You can delete that condition and the result will be identical.
x=231
res=''
if x < 0:
y=str(x)[1::]
for i in reversed(y):
res=res+str(i)
ans=res.strip('0')
if -2**31
I wonder, how can someone possibly remember these values during a real interview?
Why is this problem under Bit manipulation?
great, thank you.
Why can't we just check if number is greater than Int. MAX-VALUE and if this is the case return 0?
Because the problem description says:
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
I.e. only use 32-bit integers or smaller. MAX is literally the maximum value you can store in a 32-bit signed integer, it's impossible that any signed 32-bit could be greater than it. If you have a number that is bigger that it, you already broke the rules.
thanks
"Python is dumb" killed me😂😂. Thanks for the great explanation
This problem shouldn't be in the roadmap of bit manipulation.
Why doesn't this approach work in JavaScript?
thanks man
I have a better logic guys:
def reverse(self, x: int) -> int:
if x>=0:
val = int(str(x)[::-1])
return val if -2**31
This doesn't adhere to the 32-bit constraint.
you will get the error for negative value for this problem in this solution
Adbuuutttt!!!! amazing video
nice
nahi samajh aaya
I have implemented a different solution which for me was simpler to code and understand.
I was simply undoing the last operation and checking if it gives me my previous result.
for example if before reversing my last digit the result so far was 96463243, and the last digit to add was a 0
I would say: if (96463243*10/10 == 96463243) return 0;
If after multiplying by 10 an overflow happens (which does in the example above) the entire integer will be different
if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):
Why did you use // 10 and % 10 instead of fmod and int(/) trick? cos MIN % 10 would give you positive number. Let's say x = -2147483649 (below MIN) x % 10 would be 1 instead of -9
and MIN % 10 would be 3 instead of -7
OK + 10 still gives you the same inequalities.
Solution that works:
```
class Solution:
def reverse(self, x: int) -> int:
result = 0
MAX_INT32 = 2 ** 31 - 1 # 2147483647
MIN_INT32 = -2 ** 31 # -2147483648
MAX_INT32_DIV_10 = int(MAX_INT32 / 10)
MIN_INT32_DIV_10 = int(MIN_INT32 / 10)
LAST_DIGIT_MAX_INT32 = MAX_INT32 % 10
LAST_DIGIT_MIN_INT32 = int(math.fmod(MIN_INT32, 10))
while x != 0:
if result > MAX_INT32_DIV_10 or result < MIN_INT32_DIV_10:
return 0
digit = int(math.fmod(x, 10))
x = int(x / 10)
result = result * 10 + digit
return result;
```
How can the input be integer and be *8463847412* if it exceeds 2^31 ?
The input x cannot be 8463847412, because the given constraints are a 32-bit integer in the range of -2^31
isn't the check MIN outbound condition wrong? as MIN //10=-214748365, so with the video code never check if -214748364+last digit outbound.
good method & explain tho.
what is difference between "%" and "math.fmod" ? I was getting different answers for negative numbers by just using "%" operator.
Python's mod operation (a % b) behaves like a clock of size b. So, if you do 11 % 10 you get 1, but if you do -1 % 10 you get 9, because you wrapped around from 0 to the largest value in [0, 9]. This is useful for traversing a circular array counter-clockwise, for example, but can cause some unexpected behavior, like in this problem. The fmod function behaves like you might expect, math.fmod(-1, 10) == -1.0. It returns a float so that's why NC casted it to int.
Save yourself some time 1. This code does NOT work on LeetCode 2. There is no need to check if res == MAX // 10 for overflow, this case is covered by input itself.
My solution is just check "if (curRes / 10 != preRes) return 0"