Solution by donkikos


  • 0
    D

    Approach #1 One digit a time [Accepted]

    Intuition

    Separate one digit a time and add to the end of other integer, while checking that new number will not be out of int range.

    Algorithm

    In this approach last digit is separated from the number on each cycle of the loop and added to the beginning of the int x_rev which will store the reversed number in the end of the algorithm.

    The algorithm also checks that x_rev will not be out of int range before adding a digit to its beginning.

    C++

    int reverse(int x) {
        // return 0 if input is 0
        if (x == 0) return 0;
    
        int x2 = x, cur_d, x_rev = 0;
        int imax = std::numeric_limits<int>::max();
        int imin = std::numeric_limits<int>::min();
    
        do {
            // extract last digit
            cur_d = x2 % 10;
            // drop last digit in x2
            x2 = x2 / 10;
            // check if x_rev will be out of int range after adding cur_d to its end
            if ((x > 0 && x_rev > (imax - cur_d) / 10) || 
                (x < 0 && x_rev < (imin - cur_d) / 10)) {
                cout << "Reverse number is out of int range!!!\n";
                return 0;
            }
            // add the cur_d to the end of x_rev
            x_rev = 10 * x_rev + cur_d;
        } while (x2 != 0);
    
        // account for the sign x_rev
        return x_rev;
    }
    

    Complexity Analysis

    Here n is the number of digits in the input integer.

    • Time complexity : $$O(n)$$, as the do cycle does n loops.

    • Space complexity : $$O(1)$$, as the number of additional variables does not depend on n.


    Approach #2 Using string [Accepted]

    Algorithm

    In this approach the integer is converted to string, then reversed as a string and converted back to integer again.

    At first the number is checked to be non zero. If it is zero, there is no need to do all the following operations.

    Also, there is a chance that reversed integer might be out of range of int type. This situation is processed by capturing corresponding exception of std::stoi(string) function.

    C++

    int reverse(int x) {
        // return 0 if input is 0
        if (x == 0) return 0;
        // convert to string
        auto s = std::to_string(abs(x));
        // reverse string
        std::reverse(s.begin(), s.end());
        // try converting to integer
        try {
            return x / abs(x) * std::stoi(s);
        } catch (const std::out_of_range& e) {  // catch out of range exception
            // return 0 if inversed integer is out of int range
            return 0;
        }
    }
    

    Complexity Analysis

    Here n is the number of digits in the input integer.

    • Time complexity : $$O(n)$$, as the std::reverse() function has $$O(n)$$ time complexity.

    • Space complexity : $$O(n)$$, as the algorithm needs to store string with n characters.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.