Jobs

Interviews

Discussions

Sum of Number and Its Reverse

Medium

Asked by:

4 views

Topics:

ArraysStringsTwo Pointers

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⁵

Try coding it in LeetCode

Sum of Number and Its Reverse

Medium

Asked by:

4 views

Topics:

ArraysStringsTwo Pointers

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⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the valid range for the input number num? Should I expect negative numbers, zero, or very large numbers?
If there are multiple numbers that satisfy the condition, should I return any of them, or is there a specific one I should prioritize?
If no integer exists such that the sum of the integer and its reverse equals num, what should the function return?
Can you provide a few examples of input and expected output?
For very large numbers, how should I handle potential integer overflow issues when reversing the number?

Brute Force Solution

Approach

The brute force approach means we will check every number smaller than the input number. For each of those smaller numbers, we will calculate its reverse and then add it to the original number to see if it equals our input number.

Here's how the algorithm would work step-by-step:

Start with the number one.
Find the reverse of this number.
Add the number and its reverse together.
Check if the sum is equal to our input number.
If it is, we found a solution, and we are done.
If it isn't, move on to the next number (two, three, four, and so on).
Repeat this process of reversing, adding, and checking until we either find a solution or we reach the input number itself.
If we reach the input number and still haven't found a solution, it means there is no number that, when added to its reverse, equals the input number.

Code Implementation

def sum_of_number_and_its_reverse_brute_force(input_number):
    current_number = 1

    while current_number < input_number:
        # Convert the current number to a string so it can be reversed.
        string_representation = str(current_number)
        reversed_string = string_representation[::-1]

        # Convert the reversed string back to an integer for addition.
        reversed_number = int(reversed_string)
        sum_of_numbers = current_number + reversed_number

        # Check if the sum is equal to the input number
        if sum_of_numbers == input_number:
            return True

        current_number += 1

    # No solution was found.
    return False

Big(O) Analysis

Time Complexity

O(n*log(n)) – The brute force approach iterates from 1 up to n (exclusive), where n is the input number. For each number in this range, the algorithm reverses the number. Reversing a number requires iterating through its digits, and the number of digits in a number x is proportional to log(x). Therefore, the cost of reversing a number is O(log(x)), where x is the current number. Since x is at most n, reversing takes O(log(n)). We perform this reversal and addition O(log(n)) operation for each of the n numbers we test, leading to a total time complexity of approximately n * log(n). Thus, the overall time complexity is O(n*log(n)).

Space Complexity

O(1) – The algorithm calculates the reverse of a number within the loop and adds it to the original number. The only variables needed are for the current number being checked, its reverse, and the sum. These variables consume a constant amount of extra space, regardless of the input number N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find how many numbers can be written as the sum of themselves and their reverse, excluding numbers that end in zero. We'll focus on cleverly constructing possible sums and verifying if they can be achieved, instead of checking every single number below the given limit.

Here's how the algorithm would work step-by-step:

Start by considering the possible structures of the numbers that can be expressed as the sum of a number and its reverse.
Realize that the last digit of the original number plus the first digit (which becomes the last digit of the reverse) needs to result in the last digit of the sum. This helps limit possibilities.
Build potential original numbers based on possible combinations of digits that satisfy the above condition.
For each potential number, reverse it and calculate the sum of the original number and its reverse.
Check if the calculated sum is equal to or less than the input number. If not, skip it.
Also, make sure the original number does not end with zero.
If the sum is within the limit and the original number doesn't end with zero, increment a counter to keep track of the valid numbers.
Repeat this process for different structures and digit combinations to find all such numbers within the specified limit.

Code Implementation

def sum_of_number_and_reverse(input_number):
    count = 0

    for i in range(1, input_number + 1):
        # Exclude numbers ending in zero as per the problem description.
        if i % 10 == 0:
            continue

        reversed_i = int(str(i)[::-1])
        sum_of_i_and_reversed_i = i + reversed_i

        # Only count the numbers within the input_number limit
        if sum_of_i_and_reversed_i <= input_number:
            count += 1

    return count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through potential original numbers by constructing them based on the digits of the input number 'n'. For each digit place in the potential number, it explores a limited set of digit combinations (0-9), thus the number of potential numbers to check is proportional to the number of digits of 'n', which is logarithmic to 'n'. However, the most significant operation is determining valid combinations up to the input number 'n' . Checking the number, reversing it and computing the sum takes constant time. Therefore, the time complexity approximates to O(n) since in the worst case scenario, it must examine numbers up to 'n'.

Space Complexity

O(1) – The described solution focuses on constructing potential numbers and calculating their sums directly. It doesn't involve storing a large collection of numbers or intermediate results in auxiliary data structures like arrays or hash maps. The algorithm primarily uses a few variables to hold the potential number, its reverse, and their sum during the construction and validation process, which requires constant extra space regardless of the input number N. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input number is 0	Return true immediately as 0 + reverse(0) = 0
Input number is negative	Return false, as reversing a negative number and adding it will never equal a positive number.
Input number consists of all 0s (e.g., 000)	Treat as 0 after removing leading zeros during the reverse operation
Input number is a palindrome	Check if num+num equals original number to return true, if not then proceed with normal reverse process
Input number results in integer overflow upon reversal	Catch the overflow exception or check if reversed number is too large, returning false in these cases.
Input is a very large number close to integer limits	Be mindful of potential integer overflow during the addition of the number and its reverse.
The reverse operation results in a number with leading zeros	Ensure the leading zeros are trimmed from reversed number before addition to avoid incorrect result
No solution exists (e.g., very large number)	Return false when iterating through all possible numbers up to the input number produces no solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the valid range for the input number num? Should I expect negative numbers, zero, or very large numbers?
If there are multiple numbers that satisfy the condition, should I return any of them, or is there a specific one I should prioritize?
If no integer exists such that the sum of the integer and its reverse equals num, what should the function return?
Can you provide a few examples of input and expected output?
For very large numbers, how should I handle potential integer overflow issues when reversing the number?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number one.
Find the reverse of this number.
Add the number and its reverse together.
Check if the sum is equal to our input number.
If it is, we found a solution, and we are done.
If it isn't, move on to the next number (two, three, four, and so on).
Repeat this process of reversing, adding, and checking until we either find a solution or we reach the input number itself.
If we reach the input number and still haven't found a solution, it means there is no number that, when added to its reverse, equals the input number.

Code Implementation

def sum_of_number_and_its_reverse_brute_force(input_number):
    current_number = 1

    while current_number < input_number:
        # Convert the current number to a string so it can be reversed.
        string_representation = str(current_number)
        reversed_string = string_representation[::-1]

        # Convert the reversed string back to an integer for addition.
        reversed_number = int(reversed_string)
        sum_of_numbers = current_number + reversed_number

        # Check if the sum is equal to the input number
        if sum_of_numbers == input_number:
            return True

        current_number += 1

    # No solution was found.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the possible structures of the numbers that can be expressed as the sum of a number and its reverse.
Realize that the last digit of the original number plus the first digit (which becomes the last digit of the reverse) needs to result in the last digit of the sum. This helps limit possibilities.
Build potential original numbers based on possible combinations of digits that satisfy the above condition.
For each potential number, reverse it and calculate the sum of the original number and its reverse.
Check if the calculated sum is equal to or less than the input number. If not, skip it.
Also, make sure the original number does not end with zero.
If the sum is within the limit and the original number doesn't end with zero, increment a counter to keep track of the valid numbers.
Repeat this process for different structures and digit combinations to find all such numbers within the specified limit.

Code Implementation

def sum_of_number_and_reverse(input_number):
    count = 0

    for i in range(1, input_number + 1):
        # Exclude numbers ending in zero as per the problem description.
        if i % 10 == 0:
            continue

        reversed_i = int(str(i)[::-1])
        sum_of_i_and_reversed_i = i + reversed_i

        # Only count the numbers within the input_number limit
        if sum_of_i_and_reversed_i <= input_number:
            count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input number is 0	Return true immediately as 0 + reverse(0) = 0
Input number is negative	Return false, as reversing a negative number and adding it will never equal a positive number.
Input number consists of all 0s (e.g., 000)	Treat as 0 after removing leading zeros during the reverse operation
Input number is a palindrome	Check if num+num equals original number to return true, if not then proceed with normal reverse process
Input number results in integer overflow upon reversal	Catch the overflow exception or check if reversed number is too large, returning false in these cases.
Input is a very large number close to integer limits	Be mindful of potential integer overflow during the addition of the number and its reverse.
The reverse operation results in a number with leading zeros	Ensure the leading zeros are trimmed from reversed number before addition to avoid incorrect result
No solution exists (e.g., very large number)	Return false when iterating through all possible numbers up to the input number produces no solution.