Sum of Number and Its Reverse

MEDIUM

Description

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

Checkout 2 different approaches to solve Sum of Number and Its Reverse. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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.

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 Analysis

Time Complexity: 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 Complexity: O(1). We only use a few variables for the loop and calculation, requiring constant extra space.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Sum of Number and Its Reverse. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Sum of Number and Its Reverse

Patterns:

MathEnumeration