Sum of Number and Its Reverse

Med

#2227Time: O(N * log N), where N is the input `num`. The loop runs N+1 times. Inside the loop, reversing the number `i` takes time proportional to the number of its digits, which is O(log i). The total time is dominated by the largest numbers, so it's O(N * log N).Space: O(1). We only use a few variables for the loop and calculation, requiring constant extra space.

Patterns

Math Enumeration

Prompt

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 <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible candidate integers x from 0 up to num. For each x, it computes its reverse and checks if their sum equals num. If a match is found, it returns true. If the loop completes without finding any such x, it returns false.

Algorithm

Iterate through integers i from 0 to num.
In each iteration, compute reverse(i).
Check if i + reverse(i) == num.
If true, return true.
If the loop completes, return false.

Walkthrough

The core idea is to test every possible non-negative integer x that could be part of the sum. Since x and reverse(x) are both non-negative, if x + reverse(x) = num, then x cannot be greater than num. This gives us a search space for x from 0 to num.

The algorithm is as follows:

Loop through each integer i from 0 to num.
For each i, calculate its reverse, let's call it rev_i. A helper function can be used for this. To reverse an integer n, we can repeatedly take the last digit (n % 10) and append it to a new number, then remove the last digit from n (n / 10) until n becomes 0.
Check if i + rev_i is equal to num.
If the sum is equal to num, we have found a valid pair, so we can immediately return true.
If the loop finishes without finding any such i, it means no such number exists, and we return false.

For example, if num = 443, the loop will check i = 0, 1, 2, .... When it reaches i = 172, it calculates reverse(172) = 271. The sum is 172 + 271 = 443, which matches num. The function then returns true.

1class Solution {2    private int reverse(int n) {3        int reversed = 0;4        while (n > 0) {5            reversed = reversed * 10 + n % 10;6            n /= 10;7        }8        return reversed;9    }10 11    public boolean sumOfNumberAndReverse(int num) {12        for (int i = 0; i <= num; i++) {13            if (i + reverse(i) == num) {14                return true;15            }16        }17        return false;18    }19}

Complexity

Time

O(N * log N), where N is the input `num`. The loop runs N+1 times. Inside the loop, reversing the number `i` takes time proportional to the number of its digits, which is O(log i). The total time is dominated by the largest numbers, so it's O(N * log N).

Space

O(1). We only use a few variables for the loop and calculation, requiring constant extra space.

Trade-offs

Pros

Simple to understand and implement.
Correct for all cases within the given constraints.

Cons

Less efficient than the optimized approach as it iterates through a larger range of numbers.

This approach improves upon the simple brute force by reducing the search space. Instead of checking all integers from 0 to num, it only checks from num / 2 to num. This optimization is based on the property that if a solution x exists, then either x or reverse(x) must be greater than or equal to num / 2.

Algorithm

Iterate through integers i from num / 2 to num.
In each iteration, compute reverse(i).
Check if i + reverse(i) == num.
If true, return true.
If the loop completes, return false.

Walkthrough

This approach improves upon the simple brute force by reducing the search space. The logic relies on a key observation: if a solution x exists such that x + reverse(x) = num, then we only need to search for x in the range [num / 2, num].

Proof: Let x be a solution.

Case 1: x does not end with 0. Let y = reverse(x). Then reverse(y) = x. Since x + y = num, y is also a solution (y + reverse(y) = num). As x + y = num, at least one of them must be >= num / 2. So our search in [num / 2, num] will find either x or y.
Case 2: x ends with 0. Let x = 10k. It can be proven that x >= (x + reverse(x)) / 2, which means x >= num / 2. So our search will find x.

Based on this, it's sufficient to search the upper half of the potential range. The algorithm is:

Loop through each integer i from num / 2 to num.
For each i, calculate its reverse, rev_i.
Check if i + rev_i equals num.
If a match is found, return true.
If the loop completes, return false.

1class Solution {2    private int reverse(int n) {3        int reversed = 0;4        while (n > 0) {5            reversed = reversed * 10 + n % 10;6            n /= 10;7        }8        return reversed;9    }10 11    public boolean sumOfNumberAndReverse(int num) {12        // We search from num/2 to num. If a solution x exists,13        // either x or reverse(x) must be in this range.14        for (int i = num / 2; i <= num; i++) {15            if (i + reverse(i) == num) {16                return true;17            }18        }19        // The loop handles num=0 correctly. For num=0, i=0, 0+rev(0)=0, returns true.20        // For other cases where no solution is found, it correctly returns false.21        return false;22    }23}

Complexity

Time

O(N * log N), where N is `num`. The loop runs about N/2 times. The work inside is O(log N). While asymptotically the same as the naive approach, it is practically twice as fast.

Space

O(1). Constant extra space is used.

Trade-offs

Pros

More efficient than the basic brute force by halving the search space.
Still simple to implement.

Cons

The reasoning for the optimization is slightly more complex.
The asymptotic time complexity is not improved over the naive approach.

Solutions

Solution

1class Solution {2public3  boolean sumOfNumberAndReverse(int num) {4    for (int x = 0; x <= num; ++x) {5      int k = x;6      int y = 0;7      while (k > 0) {8        y = y * 10 + k % 10;9        k /= 10;10      }11      if (x + y == num) {12        return true;13      }14    }15    return false;16  }17}

1class Solution {2public:3  bool sumOfNumberAndReverse(int num) {4    for (int x = 0; x <= num; ++x) {5      int k = x;6      int y = 0;7      while (k > 0) {8        y = y * 10 + k % 10;9        k /= 10;10      }11      if (x + y == num) {12        return true;13      }14    }15    return false;16  }17};

1class Solution:2    def sumOfNumberAndReverse(self, num: int) -> bool: return any(3        k + int(str(k)[:: - 1]) == num for k in range(num + 1))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem