Watch 8 video solutions for Sum of Number and Its Reverse, a medium level problem involving Math, Enumeration. This walkthrough by Bro Coders has 1,870 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a non-negative integer num, return true if num can be expressed as the sum of any non-negative integer and its reverse, or false otherwise.
Example 1:
Input: num = 443 Output: true Explanation: 172 + 271 = 443 so we return true.
Example 2:
Input: num = 63 Output: false Explanation: 63 cannot be expressed as the sum of a non-negative integer and its reverse so we return false.
Example 3:
Input: num = 181 Output: true Explanation: 140 + 041 = 181 so we return true. Note that when a number is reversed, there may be leading zeros.
Constraints:
0 <= num <= 105Problem Overview: Given an integer num, determine whether there exists a non‑negative integer x such that x + reverse(x) = num. The task is simply to test if any candidate number produces the required sum when its digits are reversed.
Approach 1: Brute Force Iteration and Reversal (O(n log n) time, O(1) space)
Iterate through every possible value x from 0 to num. For each candidate, compute its digit reversal and check whether x + reverse(x) equals num. Reversing digits requires repeatedly extracting digits using modulus and division, which costs O(log n) time per number because the number of digits grows logarithmically. This approach is straightforward and relies purely on enumeration combined with basic math operations. Since only a few variables are used during digit reversal, the space complexity stays O(1).
This method works well because the search space is bounded: if x > num, then x + reverse(x) must also exceed num. Therefore testing all values up to num guarantees that every valid candidate is checked.
Approach 2: Optimized Iteration with Early Break (O(n log n) time, O(1) space)
The optimized version keeps the same enumeration strategy but introduces simple pruning during iteration. Since reverse(x) is always non‑negative, once x itself becomes greater than num, the sum x + reverse(x) must exceed num. The loop can therefore safely restrict candidates to the range 0..num and stop immediately if the current candidate cannot possibly form the required sum.
During each iteration, compute the reversed number using digit extraction and check the equation x + reverse(x) == num. If a match appears, return true immediately. If the loop completes without finding a valid candidate, return false. The complexity remains O(n log n) because each iteration still performs a digit reversal, but the early termination avoids unnecessary checks in practice.
Recommended for interviews: The enumeration approach is exactly what most interviewers expect. The brute force version demonstrates that you recognized the bounded search space and know how to implement digit reversal. Adding the early break shows awareness of constraints and small optimizations. Since the problem is primarily about reasoning with numbers rather than advanced data structures, a clean math and enumeration implementation with O(n log n) time and O(1) space is considered the correct solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Iteration and Reversal | O(n log n) | O(1) | Best baseline solution when exploring all candidates directly |
| Optimized Iteration with Early Break | O(n log n) | O(1) | Preferred in interviews to avoid unnecessary checks while keeping the logic simple |