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)
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
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 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.
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.
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
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.
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 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...
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.
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.
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.
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; }
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.
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
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?
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
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.
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; } } }
``` 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.
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
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
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
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
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: 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
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
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
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.
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 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
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
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.
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.
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.
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.
