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.
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)
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!
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
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...
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
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
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.
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.
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?
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; }
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.
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; } } }
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.
By taking absolute value of x, there is no need to check for the lower bound MIN during the reversal process. We're only concerned with the positive overflow because once we've reversed the digits we can multiply by -1 if x was originally 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.
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.
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.
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
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
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
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
`fmod` preserves negative numbers whereas % modulo doesn't - so `x % 10` and `int(math.fmod(x,10))` aren't equivalent. `x % 10` can be represented as `result = x - (10 * floor(x/10))` whereas... `math.fmod(x,10)` can be represented as `result = x - (10 * trunc(x/10))` So you would have had a headache when using negative numbers.
class Solution { public: int reverse(int x) { // Initialize a variable to hold the reversed number int reversed = 0;
// Iterate through the digits of the number while it's not zero while (x != 0) { // Extract the last digit of the current number int digit = x % 10; // `x % 10` gives the remainder when divided by 10, which is the last digit
/* * Mistake in the original implementation: * In the previous version, overflow/underflow checks were done after the multiplication * and addition (i.e., after `reversed * 10 + digit`), which could already cause undefined behavior * if the multiplication itself overflowed. This led to runtime errors in edge cases where `reversed * 10` * or the addition exceeded the 32-bit integer limit. * * Fix: * To prevent overflow or underflow, we check the conditions *before* performing the multiplication * and addition. This ensures the operations remain within the valid range of a 32-bit signed integer. */ // Check for overflow or underflow before multiplying by 10 // Explanation: // - We need to ensure that multiplying `reversed` by 10 and adding `digit` will not exceed the range // of a 32-bit signed integer, which is [-2,147,483,648, 2,147,483,647]. // - For positive numbers: // * If `reversed > INT_MAX / 10`, multiplying it by 10 would exceed `INT_MAX`, causing overflow. // * If `reversed == INT_MAX / 10`, adding a digit greater than 7 would also cause overflow // (since INT_MAX = 2,147,483,647, and the last digit is 7). // - For negative numbers: // * If `reversed < INT_MIN / 10`, multiplying it by 10 would exceed `INT_MIN`, causing underflow. // * If `reversed == INT_MIN / 10`, adding a digit less than -8 would also cause underflow // (since INT_MIN = -2,147,483,648, and the last digit is -8). if (reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && digit > 7)) { return 0; // Positive overflow detected } if (reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && digit < -8)) { return 0; // Negative overflow detected }
// Update the reversed number // Explanation: // - Multiply the current `reversed` value by 10, effectively shifting its digits one position to the left. // - Add the current digit (`digit`) to the result, placing it in the least significant position. // - This step reconstructs the reversed number incrementally as we process each digit from the input. reversed = reversed * 10 + digit; // Remove the last digit from x by dividing it by 10 // Explanation: // - Integer division by 10 discards the least significant digit from `x`. // - This allows us to continue processing the next digit in the subsequent iteration. x /= 10; }
// Return the final reversed number return reversed; } };
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
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
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
``` 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.
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.
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?
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.
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
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 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
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.
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
Can someone tell me why can't it be as simple as this: def reverse(self, x: int) -> int: res=0 while x: digit=int(math.fmod(x,10)) x=int(x/10) res=(res*10)+digit if res > 2147483647 or res < -2147483648: return 0 else: return res
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.
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.
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.
Just finished this problem as the final problem of the NeetCode 150! Neetcode ALL TIME!
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.
yes, because if it is equal to 7 so it is positive int max so it is valid .
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.
our guy is getting more popular :)
🤓
I searched if you had solved this question just last night. You read my mind!
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)
finally a correct solution I was looking for. Thanks for the explanation.
I think MIN should also use int(math.fmod(MIN, 10)) and int(MIN / 10)
Yep
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!
I think this guy's solutions are the best
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
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
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
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.
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
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.
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?
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;
}
Thanks for solving the problem. Can you provide detail on where bit manipulatin is used while reversing integer?
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
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
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
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.
By taking absolute value of x, there is no need to check for the lower bound MIN during the reversal process. We're only concerned with the positive overflow because once we've reversed the digits we can multiply by -1 if x was originally negative.
Check if negative, convert to string, reverse digits, convert back to number
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
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
class Solution:
def reverse(self, x: int) -> int:
if x > 0: # handle positive numbers
a = int(str(x)[::-1])
if x
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
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
Clear explanation for integer overflow !
Thx !
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 edge case example is wrong , the input is also beyond integer limit 5:08
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
I found this a really helpful explanation.
@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
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
LeetCode problem 7 Reverse Integer - difficulty is now Medium
That's good, it's definitely not easy
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
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
great explanation. thanks for all the efforts
`fmod` preserves negative numbers whereas % modulo doesn't - so `x % 10` and `int(math.fmod(x,10))` aren't equivalent.
`x % 10` can be represented as `result = x - (10 * floor(x/10))`
whereas...
`math.fmod(x,10)` can be represented as `result = x - (10 * trunc(x/10))`
So you would have had a headache when using negative numbers.
class Solution {
public:
int reverse(int x) {
// Initialize a variable to hold the reversed number
int reversed = 0;
// Iterate through the digits of the number while it's not zero
while (x != 0) {
// Extract the last digit of the current number
int digit = x % 10; // `x % 10` gives the remainder when divided by 10, which is the last digit
/*
* Mistake in the original implementation:
* In the previous version, overflow/underflow checks were done after the multiplication
* and addition (i.e., after `reversed * 10 + digit`), which could already cause undefined behavior
* if the multiplication itself overflowed. This led to runtime errors in edge cases where `reversed * 10`
* or the addition exceeded the 32-bit integer limit.
*
* Fix:
* To prevent overflow or underflow, we check the conditions *before* performing the multiplication
* and addition. This ensures the operations remain within the valid range of a 32-bit signed integer.
*/
// Check for overflow or underflow before multiplying by 10
// Explanation:
// - We need to ensure that multiplying `reversed` by 10 and adding `digit` will not exceed the range
// of a 32-bit signed integer, which is [-2,147,483,648, 2,147,483,647].
// - For positive numbers:
// * If `reversed > INT_MAX / 10`, multiplying it by 10 would exceed `INT_MAX`, causing overflow.
// * If `reversed == INT_MAX / 10`, adding a digit greater than 7 would also cause overflow
// (since INT_MAX = 2,147,483,647, and the last digit is 7).
// - For negative numbers:
// * If `reversed < INT_MIN / 10`, multiplying it by 10 would exceed `INT_MIN`, causing underflow.
// * If `reversed == INT_MIN / 10`, adding a digit less than -8 would also cause underflow
// (since INT_MIN = -2,147,483,648, and the last digit is -8).
if (reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && digit > 7)) {
return 0; // Positive overflow detected
}
if (reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && digit < -8)) {
return 0; // Negative overflow detected
}
// Update the reversed number
// Explanation:
// - Multiply the current `reversed` value by 10, effectively shifting its digits one position to the left.
// - Add the current digit (`digit`) to the result, placing it in the least significant position.
// - This step reconstructs the reversed number incrementally as we process each digit from the input.
reversed = reversed * 10 + digit;
// Remove the last digit from x by dividing it by 10
// Explanation:
// - Integer division by 10 discards the least significant digit from `x`.
// - This allows us to continue processing the next digit in the subsequent iteration.
x /= 10;
}
// Return the final reversed number
return reversed;
}
};
Thanks for the wonderful explanation!
simpler logic, for x > 0, pop = x % 10,
if ( rev > (INT_MAX - pop)//10 ) :
return 0;
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.
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
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
can you make more videos on bit manipulation XOR such as missing number (268) please
```
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.
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 ?
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.
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?
Use return res if abs(res) < 0x80000000 else 0
or you can use return res if abs(res)
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.
If Reverse is not able to fit in 32-bit. How come Input fit in 32-bit integer?
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
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;
}
}
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
Good explanation, thanks
NICE SUPER EXCELLENT MOTIVATED
div in python of negative numbers is giving different answer(not python3**)
They've updated this to be a medium problem now in leetcode
Why is this problem under Bit manipulation?
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
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.
Adbuuutttt!!!! amazing video
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.
leetcode turn this question level form easy to median
Why doesn't this approach work in JavaScript?
"Python is dumb" killed me😂😂. Thanks for the great explanation
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.
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?
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.
This problem shouldn't be in the roadmap of bit manipulation.
great, thank you.
you will get the error for negative value for this problem in this solution
thanks man
thanks
nahi samajh aaya
nice
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
Can someone tell me why can't it be as simple as this:
def reverse(self, x: int) -> int:
res=0
while x:
digit=int(math.fmod(x,10))
x=int(x/10)
res=(res*10)+digit
if res > 2147483647 or res < -2147483648:
return 0
else:
return res
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
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.
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.
My solution is just check "if (curRes / 10 != preRes) return 0"
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;
```
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.
thanks