Scale Engineer

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
MathEnumeration

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 <= 105

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.

class Solution {    private int reverse(int n) {        int reversed = 0;        while (n > 0) {            reversed = reversed * 10 + n % 10;            n /= 10;        }        return reversed;    }     public boolean sumOfNumberAndReverse(int num) {        for (int i = 0; i <= num; i++) {            if (i + reverse(i) == num) {                return true;            }        }        return false;    }}

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.

Solutions

class Solution {public  boolean sumOfNumberAndReverse(int num) {    for (int x = 0; x <= num; ++x) {      int k = x;      int y = 0;      while (k > 0) {        y = y * 10 + k % 10;        k /= 10;      }      if (x + y == num) {        return true;      }    }    return false;  }}

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 →

Next problem