Problem Description

Given a non-negative integer num, determine if it can be expressed as the sum of any non-negative integer and its reverse. Return true if such a pair exists, otherwise return false.

For example, if num = 443, we need to check if there exists a non-negative integer k such that k + reverse(k) = 443. In this case, k = 221 works because 221 + 122 = 443, where 122 is the reverse of 221.

The solution uses brute force enumeration to check all possible values of k from 0 to num. For each value k, it calculates the reverse of k by converting it to a string, reversing the string using slicing [::-1], and converting back to an integer. If k + reverse(k) equals num for any value of k, the function returns true.

The key insight is that if such a pair exists, at least one number in the pair must be less than or equal to num, so checking all values from 0 to num is sufficient to find the answer.

Intuition

When we need to find if a number can be expressed as the sum of some integer and its reverse, we need to think about the search space. If num = k + reverse(k) for some non-negative integer k, then k must be at most num (since both k and reverse(k) are non-negative).

This immediately gives us a bounded search space: we only need to check values of k from 0 to num. We don't need to check beyond num because if k > num, then k + reverse(k) would definitely be greater than num.

The brute force approach becomes viable because:

1. We have a finite, bounded search space [0, num]
2. For each candidate k, checking if k + reverse(k) = num is a simple O(log k) operation (to reverse the digits)
3. We can stop as soon as we find any valid k

The elegance of this solution lies in recognizing that we don't need any complex mathematical properties or optimizations - a simple exhaustive search within the bounded range is sufficient and straightforward to implement. The any() function in Python makes this even more concise, as it will return true as soon as it finds the first valid k, providing short-circuit evaluation.

Learn more about Math patterns.

Solution Approach

The solution implements a brute force enumeration strategy to check all possible values of k in the range [0, num].

The implementation uses a generator expression with Python's any() function:

any(k + int(str(k)[::-1]) == num for k in range(num + 1))

Let's break down the algorithm step by step:

1. Iterate through candidates: Use range(num + 1) to generate all integers from 0 to num inclusive.

2. Reverse each number: For each candidate k:

   • Convert k to a string: str(k)
   • Reverse the string using slice notation: str(k)[::-1]
   • Convert the reversed string back to an integer: int(str(k)[::-1])

3. Check the condition: Calculate k + reverse(k) and compare it with num.

4. Short-circuit evaluation: The any() function returns true as soon as it finds the first k where k + reverse(k) == num. If no such k exists after checking all values, it returns false.

The time complexity is O(n × log n), where n is the input num. We iterate through n+1 values, and for each value, reversing the digits takes O(log k) time (proportional to the number of digits).

The space complexity is O(log n) for storing the string representation of numbers during the reversal process.

This brute force approach is practical because the search space is naturally bounded by the input value, and the reversal operation is computationally inexpensive.

Example Walkthrough

Let's walk through the solution with num = 443:

We need to find if there exists a non-negative integer k such that k + reverse(k) = 443.

The algorithm checks each value from 0 to 443:

• k = 0: reverse(0) = 0, so 0 + 0 = 0 ≠ 443
• k = 1: reverse(1) = 1, so 1 + 1 = 2 ≠ 443
• k = 2: reverse(2) = 2, so 2 + 2 = 4 ≠ 443
• ...
• k = 220: reverse(220) = 022 = 22, so 220 + 22 = 242 ≠ 443
• k = 221: reverse(221) = 122, so 221 + 122 = 443 ✓

When we reach k = 221, we find that 221 + 122 = 443, which equals our target. The any() function immediately returns true without checking the remaining values from 222 to 443.

Let's trace through the reversal process for k = 221:

1. Convert to string: "221"
2. Reverse using [::-1]: "122"
3. Convert back to integer: 122
4. Check: 221 + 122 = 443 = num ✓

For a number where no such pair exists, like num = 11, the algorithm would check:

• k = 0: 0 + 0 = 0 ≠ 11
• k = 1: 1 + 1 = 2 ≠ 11
• k = 2: 2 + 2 = 4 ≠ 11
• ...
• k = 10: 10 + 01 = 10 + 1 = 11 ✓

So num = 11 would return true because k = 10 works.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n), where n is the value of num.

The algorithm iterates through all integers from 0 to num (inclusive), which gives us O(n) iterations. For each iteration value k, we perform:

• Converting k to a string: O(log k) time (number of digits in k)
• Reversing the string: O(log k) time
• Converting the reversed string back to integer: O(log k) time
• Addition and comparison: O(1) time

Since k can be at most n, the operations inside the loop take O(log n) time in the worst case. Therefore, the overall time complexity is O(n × log n).

Space Complexity: O(log n)

The space is used for:

• The string representation of k: O(log k) space, which is at most O(log n)
• The reversed string: O(log k) space, which is at most O(log n)
• The generator expression uses constant additional space due to the any() function evaluating lazily

The space complexity is dominated by the string operations, resulting in O(log n) total space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Range Bound

The current solution checks all values from 0 to num, but this is unnecessarily large. Since we need k + reverse(k) = num, and reverse(k) has at most the same number of digits as k, we can establish that k cannot exceed num. However, a tighter bound exists: k must be at most slightly greater than num/2 in most cases.

Optimization:

def sumOfNumberAndReverse(self, num: int) -> bool:
    # More efficient: check up to num/2 + a small buffer
    # Since k + reverse(k) = num, k is roughly num/2
    upper_bound = (num // 2) + (10 ** (len(str(num)) // 2))
    return any(
        k + int(str(k)[::-1]) == num 
        for k in range(min(upper_bound, num + 1))
    )

2. Leading Zeros in Reverse

When reversing a number that ends with zeros (e.g., 120), the reverse becomes 021 which is interpreted as 21. This is actually correct behavior for the problem, but developers might mistakenly think they need special handling.

Clarification: No fix needed - Python's int() automatically handles leading zeros correctly:

# This works correctly:
k = 120
reverse_k = int(str(k)[::-1])  # Results in 21, not 021

3. Edge Case: num = 0

The solution correctly handles num = 0 (returns True since 0 + 0 = 0), but some might overlook testing this edge case or try to add unnecessary special handling.

4. Memory vs Speed Trade-off

Converting to string for reversal is convenient but creates temporary string objects. For problems with strict memory constraints, a mathematical approach might be preferred:

Alternative approach without string conversion:

def sumOfNumberAndReverse(self, num: int) -> bool:
    def reverse_number(n):
        result = 0
        while n > 0:
            result = result * 10 + n % 10
            n //= 10
        return result
  
    return any(
        k + reverse_number(k) == num 
        for k in range(num + 1)
    )

5. Early Termination Opportunity

The current solution doesn't exploit the fact that if k + reverse(k) > num, then all larger values of k will also exceed num (in most cases). While any() provides short-circuiting for success, we could potentially break early on failure conditions too.