Sum of Number and Its Reverse - Solution & Explanation
Problem Statement
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 <= 105
Approach Overview
Problem 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 1: Brute Force Iteration and Reversal
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.
Complexity
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.
Approach 2: Optimized Iteration with Early Break
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.
Complexity
Time Complexity: O(n / 2 * d).
Space Complexity: O(1).
Approach 3: Brute Force Enumeration
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.
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
2443. Sum of Number and Its Reverse | Leetcode Weekly 315 | LeetCode 2443 • Bro Coders • 1,902 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sum of Number and Its Reverse easy or hard?
Sum of Number and Its Reverse Python/Java solution
How to solve Sum of Number and Its Reverse in O(n)?
What is the best approach for Sum of Number and Its Reverse?
Is Sum of Number and Its Reverse asked at Google/Amazon/Meta?
What data structure is used in Sum of Number and Its Reverse?
What is the time complexity of Sum of Number and Its Reverse?
Ready to solve this problem?
Practice Sum of Number and Its Reverse with our built-in code editor and test cases.
Practice on FleetCode