We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse Integer

Number: 7

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg, Meta, Microsoft, tcs, Apple, Uber, Walmart Labs, Deloitte, Adobe, Yandex, Accenture, Yahoo, Intel, Nvidia

Problem Description

Given a signed 32-bit integer x, the task is to reverse its digits. If the reversed integer goes outside the 32-bit signed integer range [-2^31, 2^31 - 1], return 0. Note that the environment does not allow storing 64-bit integers.

Key Insights

  • The problem requires reversing the digits while preserving the sign.
  • Watch out for integer overflow due to the reversed number exceeding the 32-bit signed integer limits.
  • The approach involves repeatedly extracting the last digit from the number and appending it to a new reversed integer.
  • Overflow checks are done during each iteration before actually appending the digit.

Space and Time Complexity

Time Complexity: O(n), where n is the number of digits in the integer. Space Complexity: O(1), only constant extra space is used.

Solution

The solution uses a while loop to extract the last digit from the original number using modulo operation (x % 10) and then removes this digit using integer division (x //= 10). A reversed number is constructed by multiplying the current reversed number by 10 and adding the extracted digit. Before appending each digit, the algorithm checks if the new reversed number will overflow a 32-bit signed integer by comparing it with the thresholds derived from INT_MAX and INT_MIN. The algorithm handles negative values by working with x directly since the modulo and division operations work properly with negatives in most languages.

Code Solutions

# Function to reverse an integer
def reverse(x: int) -> int:
    # Define the maximum and minimum limits for a 32-bit signed integer
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    
    reversed_num = 0  # This will store the reversed number
    
    # Process each digit until x becomes 0
    while x != 0:
        # Pop the last digit from x
        # Use modulo 10 to get the last digit
        # For negative numbers, modulo may yield negative remainder
        pop = x % 10 if x > 0 else x % -10
        # Remove the last digit from x by integer division
        x = x // 10
       
        # Check if appending the digit would cause overflow
        if reversed_num > INT_MAX // 10 or (reversed_num == INT_MAX // 10 and pop > 7):
            return 0
        if reversed_num < INT_MIN // 10 or (reversed_num == INT_MIN // 10 and pop < -8):
            return 0
        
        # Append the digit to the reversed number
        reversed_num = reversed_num * 10 + pop
        
    return reversed_num

# Example usage:
print(reverse(123))  # Output: 321
print(reverse(-123)) # Output: -321
print(reverse(120))  # Output: 21
← Back to All Questions