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 <= 105The 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n / 2 * d).
Space Complexity: O(1).
| 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). |
8 patterns to solve 80% Leetcode problems • Sahil & Sarra • 656,660 views views
Watch 9 more video solutions →Practice Sum of Number and Its Reverse with our built-in code editor and test cases.
Practice on FleetCode