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.
The brute force approach involves iterating over all numbers from 0 to num. For each number, we'll calculate its reverse and check if the sum of the number and its reverse equals num. This approach is simple to understand but may not be the most efficient for larger values of num.
This C solution iterates over each integer from 0 up to num. For each integer i, we calculate its reverse by extracting digits from the end one by one and reconstructing the reversed number. If any i and its reverse sum to num, we return true immediately; otherwise, after completion, false is returned.
Time Complexity: O(n * d), where n is num and d is the number of digits in n.
Space Complexity: O(1), constant space usage.
To optimize the iteration, we can iteratively consider only numbers whose reverses are significantly smaller. If the reversed number surpasses num/2, the iteration can break early as it's impossible for their sum to yield num from that point onward.
This C implementation stops its iteration when the reversed integer surpasses num / 2 to avoid unnecessary calculations, optimizing time while maintaining accuracy in results.
Time Complexity: O(n / 2 * d).
Space Complexity: O(1).
Enumerate k in the range [0,.., num], and check whether k + reverse(k) equals num.
The time complexity is O(n times log n), where n is the size of num.
| Approach | Complexity |
|---|---|
| Brute Force Iteration and Reversal | Time Complexity: O(n * d), where n is num and d is the number of digits in n. |
| Optimized Iteration with Early Break | Time Complexity: O(n / 2 * d). |
| Brute Force Enumeration | — |
| 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 |
2443. Sum of Number and Its Reverse | Leetcode Weekly 315 | LeetCode 2443 • Bro Coders • 1,870 views views
Watch 7 more video solutions →Practice Sum of Number and Its Reverse with our built-in code editor and test cases.
Practice on FleetCode