Sum of Number and Its Reverse

Sum of Number and Its Reverse

What is this problem about?

The "Sum of Number and Its Reverse" problem asks you to determine if a given non-negative integer num can be expressed as the sum of a non-negative integer k and its reverse. For example, if num = 443, is there a k such that k + reverse(k) = 443? In this case, if k = 172, its reverse is 271, and 172 + 271 = 443, so the answer is true.

Why is this asked in interviews?

Amazon uses this Medium-level question to test a candidate's ability to evaluate search space and implement simple digit manipulation. Since num can be up to 10^5, a simple enumeration (checking every k from 0 to num) is perfectly efficient (O(num)). It tests whether a candidate can quickly identify that a brute-force search is feasible given the constraints.

Algorithmic pattern used

The pattern is "Brute Force Enumeration with Digit Reversal."

1. Iterate through every integer i from 0 to num.
2. For each i, calculate its reverse (using the % 10 and / 10 method or string conversion).
3. Check if i + reversed_i == num.
4. If the condition is met for any i, return true. If the loop completes, return false.

Example explanation

If num = 10, let's check values:

• i = 5: reverse is 5. 5 + 5 = 10. True. If num = 63:
• Try i = 18: reverse is 81. 18 + 81 = 99 (too high).
• Try i = 58: reverse is 85. (too high). By checking all values from 0 to 63, you'll find if any sum to 63.

Common mistakes candidates make

1. Over-complicating the math: Trying to solve it using algebraic equations or digit-by-digit logic, which is much harder to implement than a simple loop.
2. Handling leading zeros incorrectly: In many languages, reversing "100" results in "1" (the number 1). You must ensure your reversal logic correctly handles this (usually mathematical reversal does this naturally).
3. Inefficient Reversal: Converting to a string, reversing the string, and converting back for every iteration. While acceptable for num = 10^5, mathematical reversal is faster.

Interview preparation tip

Always check the constraints. A constraint of 10^5 usually means an O(N) or O(N log N) solution is expected. Don't be afraid to use a simple loop if the math allows it.