Teaching Kids Programming – Sum of Number and Its Reverse (Bruteforce Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Hints:
The constraints are small enough that we can check every number.
To reverse a number, first convert it to a string. Then, create a new string that is the reverse of the first one. Finally, convert the new string back into a number.

Sum of Number and Its Reverse (Bruteforce Algorithm)

By reverse a integer, we can first convert it to string, reverse the string, and then convert it back:

def rev(i):
    return int(str(i)[::-1])

This takes O(M) time, but it requires three passes. It is slower than the following method, where we extract the least significant digit at a time:

def rev(i):
    ans = 0
    while i:
        ans = ans * 10 + i % 10
        i //= 10
    return ans

This is O(M) time and one pass – where M is the number of the digits. Then we can just bruteforce. Since two numbers are interchangeable, let’s assume they are a and b and a is not bigger than b. To avoid missing the leading zeros, we need to iterate b from the middle to the upper bound. For example, 190 reversed becomes 019.

class Solution:
    def sumOfNumberAndReverse(self, num: int) -> bool:
        for i in range(num//2, num + 1):
            if i + rev(i) == num:
                return True
        return False

The overall time complexity is O(NM).

This problem can also be solved using Math, or Binary Search – which we will cover in the future.

–EOF (The Ultimate Computing & Technology Blog) —