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

Sum of Number and Its Reverse

Number: 2541

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a non-negative integer num, determine if it can be expressed as the sum of a non-negative integer and its reverse.

Key Insights

  • The equation is x + reverse(x) = num.
  • Since both x and reverse(x) are non-negative, x must be between 0 and num.
  • Reversing a number is straightforward, with care for leading zeros in the reversed number.
  • A brute-force search from 0 to num is acceptable because num is at most 10^5.

Space and Time Complexity

Time Complexity: O(num) in the worst-case, where num ≤ 10^5. Space Complexity: O(1) since only a constant amount of extra space is used.

Solution

We iterate over all possible values of x from 0 to num. For each x, we compute its reverse and check if the sum (x + reverse(x)) equals num. The helper function to reverse a number involves converting the number to a string, reversing the string, and then converting it back to an integer. The brute-force search works given the constraint, and no additional data structures are needed.

Code Solutions

def sumOfNumberAndReverse(num: int) -> bool:
    # Helper function to reverse the integer
    def reverse_number(x: int) -> int:
        # Convert the number to string, reverse it, and then convert back to integer.
        return int(str(x)[::-1])
    
    # Iterate over the possible values from 0 to num (inclusive)
    for x in range(num + 1):
        # Check if x plus its reverse equals num
        if x + reverse_number(x) == num:
            return True
    # If no validity found, return False
    return False

# Example usage:
print(sumOfNumberAndReverse(443))  # Expected output: True
print(sumOfNumberAndReverse(63))   # Expected output: False
print(sumOfNumberAndReverse(181))  # Expected output: True
← Back to All Questions