Labels

Friday, March 13, 2015

Reverse Integer

Reverse digits of an integer.
Example1: 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