Example1: x = 123, return 321
Example2: x = -123, return -321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Naive Way: My method is to keep getting the least valuable digit from x. This method is a good approach when I implements it. But the edge case really bothers me. I manually add edge overflow cases in three parts, which is pretty bad.
public class Solution {
public int reverse(int x) {
// edge case
if(x==Integer.MIN_VALUE) return 0;
// negative number, convert from positive
if(x < 0) return -reverse(-x);
int y = 0;
for(int i = 10;x!=0;i *= 10){
// overflow
if(y > Integer.MAX_VALUE/10) return 0;
y *= 10;
y += (x%i)/(i/10);
x -= x%i;
// overflow
if(i==1000000000 && x!=0){
if(y > Integer.MAX_VALUE/10) return 0;
y *= 10;
y += x/i;
x = 0;
}
}
return y;
}
}
Improved Way: A better way is to include as many as edge case in the main loop. Then I try to get the most valuable digit first. It turns out that it's hard to deal with edge case also.
public class Solution {
static final int base = 1000000000;
public int reverse(int x) {
// edge case, overflow
if(x == Integer.MIN_VALUE) return 0;
// negative value
if(x < 0) return -reverse(-x);
int y = 0, highest = 1;
for(int i = base;i != 0;i/= 10){
// note down highest digit
if(x >= i && highest==1) highest = i;
// edge case, overflow
if(x/i > 2 && highest == base && i==1) return 0;
if(y > Integer.MAX_VALUE - x/i*(highest/i)) return 0;
y += x/i*(highest/i);
x -= x/i*i;
}
return y;
}
}
Using Double or Long can simply deal with overflow, just check the result after reverse. But I don't think that's what the question is asking.
And my first approach is a correct thinking, but not being correctly manipulated. Here is a gentle way to deal with overflow edge case.
public class Solution {
public int reverse(int x) {
// edge case
if(x==Integer.MIN_VALUE) return 0;
// negative number, convert from positive
if(x < 0) return -reverse(-x);
int y = 0;
while(x != 0){
// edge case, overflow
if(y > Integer.MAX_VALUE/10) return 0;
y *= 10;
y += x%10;
x /= 10;
}
return y;
}
}
No comments:
Post a Comment