# Sum of Number and Its Reverse
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-number-and-its-reverse)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-number-and-its-reverse
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
---
## Problem
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
## 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`.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Optimized Brute Force Iteration
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`.
**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.
**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.
### Explanation
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`.

```java
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) {
        // We search from num/2 to num. If a solution x exists,
        // either x or reverse(x) must be in this range.
        for (int i = num / 2; i <= num; i++) {
            if (i + reverse(i) == num) {
                return true;
            }
        }
        // The loop handles num=0 correctly. For num=0, i=0, 0+rev(0)=0, returns true.
        // For other cases where no solution is found, it correctly returns false.
        return false;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool 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;
  }
};

```

### Python

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

```