Solution by vitaly_bilanchuk


  • 0
    V

    Question

    Given a 32-bit signed integer, reverse digits of an integer.

    Example 1:

    Input: 123

    Output: 321

    Example 2:

    Input: -123
    Output: -321

    Example 3:

    Input: 120
    Output: 21

    Note:

    Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

    Solution

    Approach #1 Reordering

    Intuition

    Reverse number by changing digits order.

    Algorithm

    Assume that integer number X is a view of an array of digits d1, d2, ... dN. In these case the following formula is applied:

    X = ( ... ((d[1] * 10 + d[2]) * 10 + d[3] ) * 10 ... ) * 10 + d[N]; {1}

    For example:

    487 = (4 * 10 + 8) * 10 + 7 = (40 + 8) * 10 + 7 = 48 * 10 + 7= 480 + 7 = 487

    The main idea is in reversing d[...] array. In this case reverted array is dN, dN-1, ... d2, d1
    and reverted integer number RX could be found by the following formula:

    RX = ( ... ((d[N] * 10 + d[N-1]) * 10 + d[N-2] ) * 10 ... ) * 10 + d[1]; {2}

    or (after hiding brackets according the mathematical rules)

    RX = d[N] * 10^(N-1) + d[N-1] * 10^(N-2) + .. + d[1] * 10^0; {3}

    It is seen that we should go one by element ( digit ) and calculate RX by the previous formula {2} or {3}.

    A one of the good ways (easy way) of doing this is cutting elements ( digits ) from X using the remainder of division:
    The algorithm ( with an example of cutting 487 number) is the following:

    • Define the first element and its new position. An element is equal the reminder of division by 10. It is 7 for 487.
    • The position equals size of all elements in a number. Take X/10 number ( 48 in our case ) and apply the previous operation to define the next element ( digit ). Repeat it recursively and define a size for all digits and their values.
    • Make calculation of the current RX value using digit and its position
    • All digits should be involved.

    The algorithm uses recursion and has the check for overflows.
    The main idea is checking added element at the begin ( left ) of RX.

    C++

    // function for getting @dpos digit of number @x.
    int getDigit(int x, size_t dpos)
    {
        return ( x / (int) pow(10, dpos - 1) ) % 10;
    }
    
    // an iteration function. It is used to find digits and define their positions in reserved number
    int reverseIteration(int x, size_t& size)
    {
      if(x / 10 == 0)
      {
        size = 1;
        return x;
      }
      // define the last digit
      int digit = x%10;
    
      // define cut number
      int reversedSubX = reverseIteration(x/10, size);
    
      // add the digit to reversed number
      int reversedX = digit * pow(10,size) + reversedSubX;
      size++;
    
      // check overflows
      if(getDigit(reversedX, size) != digit)
      {
        return 0;
      }
      return reversedX;
    }
    int reverse(int x)
    {
    	size_t size; // number size. temporal
    	return reverseIteration(x, size);
    }
    

    Negative number: in the case of a negative number all digits and reversedSubX values are negative too.

    Complexity Analysis

    • Time complexity : $$O(n)$$ ( or $$O(1)$$ in the current case)

    We need to iterate over all elements in a number. But the task says about integer number ( n <= 10 ). So it is not too complex.

    • Space complexity : $$O(n)$$.

    We need $$O(n)$$ space for storing intermediate values ( digits, reversedX, reversedSubX).


Log in to reply
 

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