Sum of Number and Its Reverse — Problem & Solution
Sum of Number and Its Reverse solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum of Number and Its Reverse is a medium coding problem on math and enumeration, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a non-negative integer num, return true if it can be written as k + reverse(k) for some non-negative integer k.
reverse(k) is the number formed by writing the digits of k backwards; leading zeros of the result are dropped, so reverse(120) = 21.
Example 1
Input: num = 121
Output: true
Explanation: 110 + 011 = 110 + 11 = 121 (29 + 92 works too).
Example 2
Input: num = 13
Output: false
Example 3
Input: num = 0
Output: true
Explanation: 0 + 0 = 0.
Constraints
0 <= num <= 10^5
Hints for Sum of Number and Its Reverse
Hint 1
numis at most 10^5, so you can simply try everykfrom 0 tonum.Hint 2
Reversing a number is a digit loop:
r = r * 10 + k % 10, then drop the last digit ofk.Hint 3
You can start at
num / 2: if a solutionkis smaller, thenreverse(k)is larger and is itself a solution.
How to solve Sum of Number and Its Reverse
The range is small enough to try every candidate k, and half of the range can be skipped because a small solution always has a large partner.
Approach
- For
kfromfloor(num / 2)up tonum, computereverse(k)with a digit loop. - If
k + reverse(k) == num, returntrue. - If no
kworks, returnfalse.
Why it works
k + reverse(k) can only equal num for k <= num, so the full search 0..num is exhaustive. For the shortcut: if a solution has k < num / 2, then reverse(k) > num / 2 > k. A number with trailing zeros reverses to a shorter, smaller number, so k has none — which means reverse(reverse(k)) = k, and m = reverse(k) is a solution with m >= num / 2. Hence some solution always lies in the upper half.
Complexity
- Time —
O(num · log num) - Space —
O(1)
Pitfalls
- Reversal drops leading zeros of the result (
reverse(10) = 1), so10 + 1 = 11counts. num = 0is true (k = 0); make sure the loop includes it.- Do not try to reverse
numitself — the question is about the summandk.
Reference solution
Python
def sumOfNumberAndReverse(num: int) -> bool:
for k in range(num // 2, num + 1):
if k + int(str(k)[::-1]) == num:
return True
return FalseJava
public static boolean sumOfNumberAndReverse(int num) {
for (int k = num / 2; k <= num; k++) {
int r = 0, t = k;
while (t > 0) {
r = r * 10 + t % 10;
t /= 10;
}
if (k + r == num) return true;
}
return false;
}C++
bool sumOfNumberAndReverse(int num) {
for (int k = num / 2; k <= num; k++) {
int r = 0, t = k;
while (t > 0) {
r = r * 10 + t % 10;
t /= 10;
}
if (k + r == num) return true;
}
return false;
}JavaScript
var sumOfNumberAndReverse = function(num) {
for (var k = Math.floor(num / 2); k <= num; k++) {
var r = 0, t = k;
while (t > 0) {
r = r * 10 + t % 10;
t = Math.floor(t / 10);
}
if (k + r === num) return true;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.