Jobs

Interviews

Discussions

Add Strings

Easy

Airbnb

0 views

Topics:

Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

Example 1:

Input: num1 = "11", num2 = "123"
Output: "134"

Example 2:

Input: num1 = "456", num2 = "77"
Output: "533"

Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"

Constraints:

1 <= num1.length, num2.length <= 10⁴
num1 and num2 consist of only digits.
num1 and num2 don't have any leading zeros except for the zero itself.

Add Strings

Easy

Airbnb

0 views

Topics:

Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

Example 1:

Input: num1 = "11", num2 = "123"
Output: "134"

Example 2:

Input: num1 = "456", num2 = "77"
Output: "533"

Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"

Constraints:

1 <= num1.length, num2.length <= 10⁴
num1 and num2 consist of only digits.
num1 and num2 don't have any leading zeros except for the zero itself.

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:

Can num1 and num2 contain leading zeros? If so, should I remove them or handle them in the addition?
Are num1 and num2 guaranteed to be non-negative integers, or could they be negative or non-integer values?
What is the maximum possible length of num1 and num2? Is there a practical limit on the size of the numbers they represent?
If both num1 and num2 are "0", should I return "0" or is there another specific expected output?
Can num1 or num2 be null or empty strings? If so, how should I handle those cases?

Brute Force Solution

Approach

When adding strings representing numbers, the brute force approach mimics how we add numbers by hand, digit by digit. We start from the rightmost digits of both strings and work our way left, keeping track of any carry-over values. This continues until we've processed all digits of both strings and any remaining carry.

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

Start by looking at the last digit of both strings.
Add those digits together, and if the result is ten or more, remember the 'one' to carry over.
Write down the ones digit of the sum as the last digit of the answer.
Move to the next digits to the left in both strings.
Add these digits together, plus the carry-over if there was one.
Again, if the sum is ten or more, remember the 'one' to carry over.
Write down the ones digit of the sum in front of the last digit of the answer.
Keep doing this until you run out of digits in both strings.
If one string is longer than the other, keep adding the remaining digits of the longer string, along with any carry-over.
Finally, if there's still a carry-over after processing all digits, write it down at the beginning of the answer.

Code Implementation

def add_strings(number1, number2):
    result = ""
    carry = 0
    pointer1 = len(number1) - 1
    pointer2 = len(number2) - 1

    while pointer1 >= 0 or pointer2 >= 0:
        digit1 = int(number1[pointer1]) if pointer1 >= 0 else 0
        digit2 = int(number2[pointer2]) if pointer2 >= 0 else 0

        # Sum the digits and the carry
        current_sum = digit1 + digit2 + carry
        carry = current_sum // 10
        current_digit = current_sum % 10

        result = str(current_digit) + result
        
        if pointer1 >= 0:
            pointer1 -= 1

        if pointer2 >= 0:
            pointer2 -= 1

        # If there's a carry left, add it to the result
    if carry:
        result = str(carry) + result

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the two input strings, num1 and num2, performing addition digit by digit. The number of iterations is bounded by the length of the longer string, which we can denote as n. Each digit addition involves a constant number of operations. Therefore, the time complexity is directly proportional to the length of the longer string, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm builds a result string to store the sum of the two input strings. In the worst-case scenario, the sum can have a length of up to N+1 where N is the length of the longer input string, due to a potential carry-over at the most significant digit. Therefore, the space required for the result string grows linearly with the length of the input strings. The carry variable uses constant space, but the dominant factor is the result string.

Optimal Solution

Approach

We're adding two very large numbers that are represented as strings, so we can't directly use typical addition. We'll mimic the way we add numbers by hand, working from right to left, keeping track of any carry-over values.

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

Start at the far right end of both strings, which represents the ones place.
Add the digits in that place together, along with any carry-over value from the previous place.
If the sum is 10 or greater, record the ones digit of the sum as part of your result, and carry over the tens digit (which will be 1) to the next place.
If the sum is less than 10, record the sum as part of your result, and carry over zero.
Move one place to the left in both strings and repeat the addition and carry-over process.
Keep doing this until you've processed all digits in both strings.
If one string is longer than the other, continue the process with the remaining digits of the longer string, still adding in any carry-over values.
If, after processing all digits, there's still a carry-over value, add it as a leading digit to the result.
Finally, reverse the result because we built it from right to left, and that's your answer.

Code Implementation

def add_strings(number1, number2):
    result = ''
    carry = 0
    pointer1 = len(number1) - 1
    pointer2 = len(number2) - 1

    while pointer1 >= 0 or pointer2 >= 0:
        digit1 = int(number1[pointer1]) if pointer1 >= 0 else 0
        digit2 = int(number2[pointer2]) if pointer2 >= 0 else 0

        # Perform digit-wise addition with carry
        current_sum = digit1 + digit2 + carry
        carry = current_sum // 10
        current_digit = current_sum % 10
        result += str(current_digit)

        if pointer1 >= 0:
            pointer1 -= 1
        if pointer2 >= 0:
            pointer2 -= 1

    # Add the final carry if it exists
    if carry:
        result += str(carry)

    # Reverse the result string
    return result[::-1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the two input strings once, performing a constant amount of work (addition and carry handling) for each digit. The number of iterations is bounded by the length of the longer string, which we can define as n. Even if one string is significantly longer than the other, we still process at most n digits. Therefore, the time complexity is directly proportional to the length of the input strings, resulting in O(n).

Space Complexity

O(N) – The algorithm constructs a string to store the result of the addition. In the worst-case scenario, the sum of the two input strings, num1 and num2, both of length N can have N+1 digits due to a potential carry at the most significant digit. Therefore, the space required to store the result string grows linearly with the length of the input strings, represented as N. There are also a few integer variables to keep track of carry and indices but they take up constant space, which is insignificant compared to the result string. Thus, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Both num1 and num2 are empty strings	Return '0' or an empty string, depending on specification, after checking if both strings are empty.
One of the strings is empty	Return the non-empty string as the result, since adding to empty string doesn't change value.
num1 or num2 starts with leading zeros	The algorithm should correctly handle the leading zeros as they are digits in the strings.
Very large input strings that might cause integer overflow if converted to integers	The algorithm should perform digit-by-digit addition as strings to avoid integer overflow.
One string is significantly longer than the other	The algorithm must correctly handle different lengths by appropriately iterating through both strings and handling the carry.
The sum results in a carry at the most significant digit	The algorithm needs to correctly prepend the carry to the result string.
Both strings are '0'	The solution should return '0' without errors.
String containing non-digit characters	The function should validate the input strings and either throw an error or return an appropriate message if they contain non-digit characters.

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:

Can num1 and num2 contain leading zeros? If so, should I remove them or handle them in the addition?
Are num1 and num2 guaranteed to be non-negative integers, or could they be negative or non-integer values?
What is the maximum possible length of num1 and num2? Is there a practical limit on the size of the numbers they represent?
If both num1 and num2 are "0", should I return "0" or is there another specific expected output?
Can num1 or num2 be null or empty strings? If so, how should I handle those cases?

Brute Force Solution

Approach

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

Start by looking at the last digit of both strings.
Add those digits together, and if the result is ten or more, remember the 'one' to carry over.
Write down the ones digit of the sum as the last digit of the answer.
Move to the next digits to the left in both strings.
Add these digits together, plus the carry-over if there was one.
Again, if the sum is ten or more, remember the 'one' to carry over.
Write down the ones digit of the sum in front of the last digit of the answer.
Keep doing this until you run out of digits in both strings.
If one string is longer than the other, keep adding the remaining digits of the longer string, along with any carry-over.
Finally, if there's still a carry-over after processing all digits, write it down at the beginning of the answer.

Code Implementation

def add_strings(number1, number2):
    result = ""
    carry = 0
    pointer1 = len(number1) - 1
    pointer2 = len(number2) - 1

    while pointer1 >= 0 or pointer2 >= 0:
        digit1 = int(number1[pointer1]) if pointer1 >= 0 else 0
        digit2 = int(number2[pointer2]) if pointer2 >= 0 else 0

        # Sum the digits and the carry
        current_sum = digit1 + digit2 + carry
        carry = current_sum // 10
        current_digit = current_sum % 10

        result = str(current_digit) + result
        
        if pointer1 >= 0:
            pointer1 -= 1

        if pointer2 >= 0:
            pointer2 -= 1

        # If there's a carry left, add it to the result
    if carry:
        result = str(carry) + result

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the far right end of both strings, which represents the ones place.
Add the digits in that place together, along with any carry-over value from the previous place.
If the sum is 10 or greater, record the ones digit of the sum as part of your result, and carry over the tens digit (which will be 1) to the next place.
If the sum is less than 10, record the sum as part of your result, and carry over zero.
Move one place to the left in both strings and repeat the addition and carry-over process.
Keep doing this until you've processed all digits in both strings.
If one string is longer than the other, continue the process with the remaining digits of the longer string, still adding in any carry-over values.
If, after processing all digits, there's still a carry-over value, add it as a leading digit to the result.
Finally, reverse the result because we built it from right to left, and that's your answer.

Code Implementation

def add_strings(number1, number2):
    result = ''
    carry = 0
    pointer1 = len(number1) - 1
    pointer2 = len(number2) - 1

    while pointer1 >= 0 or pointer2 >= 0:
        digit1 = int(number1[pointer1]) if pointer1 >= 0 else 0
        digit2 = int(number2[pointer2]) if pointer2 >= 0 else 0

        # Perform digit-wise addition with carry
        current_sum = digit1 + digit2 + carry
        carry = current_sum // 10
        current_digit = current_sum % 10
        result += str(current_digit)

        if pointer1 >= 0:
            pointer1 -= 1
        if pointer2 >= 0:
            pointer2 -= 1

    # Add the final carry if it exists
    if carry:
        result += str(carry)

    # Reverse the result string
    return result[::-1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both num1 and num2 are empty strings	Return '0' or an empty string, depending on specification, after checking if both strings are empty.
One of the strings is empty	Return the non-empty string as the result, since adding to empty string doesn't change value.
num1 or num2 starts with leading zeros	The algorithm should correctly handle the leading zeros as they are digits in the strings.
Very large input strings that might cause integer overflow if converted to integers	The algorithm should perform digit-by-digit addition as strings to avoid integer overflow.
One string is significantly longer than the other	The algorithm must correctly handle different lengths by appropriately iterating through both strings and handling the carry.
The sum results in a carry at the most significant digit	The algorithm needs to correctly prepend the carry to the result string.
Both strings are '0'	The solution should return '0' without errors.
String containing non-digit characters	The function should validate the input strings and either throw an error or return an appropriate message if they contain non-digit characters.