LeetCode: 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?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

---

There are two trivial solutions for this problem: one is converting the integer to a string and reversing the string, then converting it back to integer. Another way is to create the result with modular arithmetic. See more discussions in the codes.

C++ Code 1:

/* 
 * func: reverse
 * goal: to reverse a integer
 * @param x: the input integer
 * return: the reversed integer
 */
/*
 * Lazy way: convert the integer to a string and reverse the string
 * Then use built-in function atoi to do the conversion
 */
int reverse(const int &x){
    //To receive the input string
    string str = std::to_string(x);
    
    std::reverse(str.begin(), str.end());
    
    return x < 0 ? -atoi(str.c_str()) : atoi(str.c_str());
}

C++ Code 2:

/*
 * func: reverse
 * goal: to reverse a integer
 * @param x: the input integer
 * return: the reversed integer
 */
int reverse(int &x){
    int ret = 0;
    while(x != 0){
        ret = ret * 10 + x % 10;
        x /= 10;
    }
    
    return ret;
}

Note: Both of these solutions can handle overflow cases. However, it is not elegant. When the number is out of range, it will output an unreasonable result. One more thing, I tested both of the codes and they showed similar performance. I think the reason is that the second one use less variable but it needs more computation works than the first one.

Below is the third solution without using built-in functions and return bounds if the reversed integer is out of range.

C++ Code 3:

/*
 * func: string_to_int
 * goal: convert string to int
 * @param str: the input string
 * return: return int
 */
int string_to_int(const string & str){
    int ret = 0;
    for(const char& c: str){
        ret = ret*10 + c - '0';
    }
    
    return ret;
}


/*
 * func: string_comp
 * goal: to compare two integer string of same length
         which is greater if converted to int
 * @param left: input string 1
 * @param right: input string 2
 * return: left is bigger or not
 * Assume the two inputs are with same length
 */
bool string_comp(const string &left, const string &right){
    for(int i=0; i<left.length(); ++i){
        if(left.at(i) < right.at(i)){
            return false;
        }else if(left.at(i) > right.at(i)){
            return true;
        }
    }
    
    return true;
}


/*
 * func: reverse
 * goal: to reverse a integer
 * @param x: the input integer
 * return: the reversed integer
 */
/*
 * Normal way: convert the integer to a string and perform a format 
 * check like 0 and bound check and then converted back to int
 */
int reverse(const int &x){
    //To receive the input integer
    string str = std::to_string(x);
    
    if(str.at(0) == '-'){
        str = str.substr(1);
    }
       
    //Get the integer bound
    string upper_bound = std::to_string(numeric_limits<int>::max());
    string lower_bound = std::to_string(numeric_limits<int>::min()).substr(1);
    
    //Reverse the string
    std::reverse(str.begin(), str.end());
    
    //Remove the 0 at the front if there exists
    while( str.length() > 1 && str.at(0) == '0'){
        str.erase(0,1);
    }
    
    //Bound check
    if(str.length() < upper_bound.length()){
        return x > 0 ? string_to_int(str) : -string_to_int(str);
    }else{
        if(string_comp(str, x > 0 ? upper_bound : lower_bound)){
            return x > 0 ? numeric_limits<int>::max() : numeric_limits<int>::min();
        }else{
            return x > 0 ? string_to_int(str) : -string_to_int(str);
        }
    }
}

There is also one thing to notice, which is the function abs(). If the input for abs is exact -2147483648, the lower bound for integer, it will still return -2147483648. That is why I choose to remove the '-' sign after the conversion.

Python Code:

# func: reverse digits of an integer
# @param x: input integer
# @return: the reversed integer
def reverse(x):
    #Convert x to string
    str_x = str(x) if x >= 0 else str(x)[1:]
    #Reverse the string
    str_x = str_x[::-1]

    return int(str_x) if x >= 0 else int(str_x) * -1

Since in Python, an negative integer divide by a positive integer whose absolute value is larger will return -1 instead of 0, like -7/10 = -1. And -123/10 = 13. It will need more considerations in python.

Reference Link:

[closed] Reverse Integer - LeetCode: http://discuss.leetcode.com/questions/191/reverse-integer