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

**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^5Hints:

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:

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

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:

1 2 3 4 5 6 |
def rev(i): ans = 0 while i: ans = ans * 10 + i % 10 i //= 10 return ans |

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.

1 2 3 4 5 6 |
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 |

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) —

**GD Star Rating***loading…*

551 words

**Last Post**: Teaching Kids Programming – Maximum Count of Positive Integer and Negative Integer in Sorted Array

Source: Internet