Solution by nikhilupadhyayan


  • 0
    N

    Approach #1 Using mod and division [Accepted]

    Intuition

    Use mod 10 to get rightmost digit. Multiple it by 10 to push it towards the left.
    Divide by 10 to remove the rightmost digit. Keep repeating these steps to obtain
    the reversed integer

    Algorithm

    1. x = given integer
    2. r = r*10 + i % 10
    3. r = r*10
    4. i = i/10
    5. Repeat steps 2-4 till i becomes 0
    6. r will be the reversed integer

    Python

    class Solution(object):
        def reverse(self, x):
            r = 0
    
            # because we are dealing with 32-bit signed integers 
            # as per the question
            maxx = pow(2,31) 
            
            sign = -1 if x<0 else 1
            
            x = abs(x)
            while x!=0:
                if (maxx-x%10)/10 < r:
                    # Requirement : maxx < r*10 + x%10 
                    #               maxx-x%10 < r*10
                    #               (maxx-x%10)/10 < r
                    # We can't check for r*10 + x%10 > maxx because
                    # r*10 + x%10 may overflow if it is greater than max 32-bit integer value
                    # in which case we can never catch the overflow
                    return 0
                r = r*10 + x%10
                x = x/10
            return sign*r
            
            
    

    Java

    import java.lang.Math;
    class Solution {
        public int reverse(int x) {
            int r = 0;
            
            int sign = x<0 ? -1 : 1;
            x = Math.abs(x);
            while (x!=0){
                
                 //Requirement : Integer.MAX_VALUE < r*10 + x%10 
                 //              Integer.MAX_VALUE-x%10 < r*10
                 //              (Integer.MAX_VALUE-x%10)/10 < r
                 //    We can't check for r*10 + x%10 > Integer.MAX_VALUE because
                 //    r*10 + x%10 may overflow if it is greater than Integer.MAX_VALUE
                 //    in which case we can never catch the overflow
                if ((Integer.MAX_VALUE - x%10)/10 < r){
                    return 0;
                }
                r = r*10 + x%10;
                x = x/10;
            }
            return sign*r;
        }
    }
    

    Complexity Analysis

    • Time complexity : O(1)

      Since we are dealing with 32-bit integers, time complexity will be constant
      irrespective of size of the integer

    • Space complexity : O(1)

      Space used is constant irrespective of how big the input integer is.

    Approach #2 String Reversal [Accepted]

    Intuition

    Consider the integer as a String and reverse the characters of the String.

    Algorithm

    1. Convert the integer into a string
    2. Remove the negative sign if present.
    3. Reverse the string.
    4. Append the negative sign (if removed in step 2) at the beginning of the String
    5. Convert string to integer
    6. If value of integer is greater than INT_MAX (2^^31) or less than INT_MIN(-2^^31), return 0
    7. Else return the value of the integer

    python

    class Solution(object):
        def reverse(self, x):
            y = str(x)
            res = 0
            if y[0] == '-':
                # negative integer. So take substring ignoring negative sign 
                # and reverse it
                res = int('-' + y[1:len(y)][::-1])
            else:
                # positive integer. Simply reverse the string
                res = int(y[::-1])
            
            maxx = 2 ** 31
            # given that integer range is 32-bit. So max value is 2**31
            if res > maxx or res < -maxx:
                return 0
            else:
                return res
    

    Complexity Analysis

    • Time complexity : O(n)

      Reversing a String has a time complexity of O(n). Hence the complexity of
      this solution is O(n)

    • Space complexity : O(1)
      No extra space is needed. Hence space complexity is constant.


Log in to reply
 

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