Problem

Given a non-negative integer num, return true ifnum _can be expressed as the sum of anynon-negative integer and its reverse, or _false otherwise.

Examples

Example 1

1
2
3

Input: num = 443
Output: true
Explanation: 172 + 271 = 443 so we return true.

Example 2

1
2
3

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

1
2
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^5

Solution

Approach

Try all possible x from 0 to num. For each x, check if x + reverse(x) == num. If so, return true. Otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    bool sumOfNumberAndReverse(int num) {
        for (int x = 0; x <= num; ++x) {
            int y = 0, t = x;
            while (t) { y = y * 10 + t % 10; t /= 10; }
            if (x + y == num) return true;
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

class Solution {
    fun sumOfNumberAndReverse(num: Int): Boolean {
        for (x in 0..num) {
            var y = 0
            var t = x
            while (t > 0) {
                y = y * 10 + t % 10
                t /= 10
            }
            if (x + y == num) return true
        }
        return false
    }
}
1
2
3
4
5
6
7

class Solution:
    def sumOfNumberAndReverse(self, num: int) -> bool:
        for x in range(num+1):
            y = int(str(x)[::-1])
            if x + y == num:
                return True
        return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn sum_of_number_and_reverse(num: i32) -> bool {
        for x in 0..=num {
            let mut y = 0;
            let mut t = x;
            while t > 0 {
                y = y * 10 + t % 10;
                t /= 10;
            }
            if x + y == num { return true; }
        }
        false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function sumOfNumberAndReverse(num: number): boolean {
    for (let x = 0; x <= num; ++x) {
        let y = 0, t = x;
        while (t > 0) {
            y = y * 10 + t % 10;
            t = Math.floor(t / 10);
        }
        if (x + y === num) return true;
    }
    return false;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)