Sunday, September 21, 2014

Algorithm: Reverse an integer

Problem: Reverse an integer
17 reverses to 71
9 reverses to 9
-2367 reverses to -7632
*** space overhead NOT allowed


This problem can be easily solved if space overhead is allowed. You can convert the integer into a string and then reverse the string and parse back string into an integer. But what makes this problem interesting is if you have to do it without any space overhead (except that of the result). Below is the Java implementation of the same. 

       * Reverse a integer (handles negatives also)  
       * @param num  
       * @return  
      public static int reverseNum(int num) {  
           boolean negative = false;  
           if (num < 0) {  
                num = -num;  
                negative = true;  
           int reverse = 0;  
           while (num > 0) {  
                reverse = reverse * 10 + num % 10;  
                num /= 10;  
           if (negative) {  
                reverse = -reverse;  
           return reverse;  

Note: What if number overflows? 
If the number overflows the reversed number will not fit in the integer data type.
One of the possible ways would be to store reversedNum in long and then check if it's value is out of integer range and then do something like below:
if(reverse > Integer.MAX_VALUE || reverse < Integer.MIN_VALUE) {
        return 0;
 } else {
        return (int) reverse;
So refactor your code to make sure that overflow is taken into consideration. There are other ways to check if number overflows (like positive number will become negative). But, I think the above approach is much cleaner.

Checking if the number is a palindrome
This method can be used to check if a number is a palindrome.
if (reverse(num) == num ){
  //num is palindrome

keep coding !!!

No comments:

Post a Comment