LeetCode 415: Add Strings

Problem Restatement

We are given two non-negative integers as strings:

num1
num2

Return their sum as a string.

We cannot use a built-in big integer library.

We also cannot directly convert the whole input strings into integers.

So this is manual addition, the same way we add numbers on paper.

The source problem states that num1 and num2 contain only digits, have no leading zeroes except "0" itself, and each length is between 1 and 10^4.

Input and Output

Example function shape:

def addStrings(num1: str, num2: str) -> str:
    ...

Examples

Example 1:

num1 = "11"
num2 = "123"

The answer is:

"134"

Manual addition:

  123
+  11
-----
  134

Example 2:

num1 = "456"
num2 = "77"

The answer is:

"533"

Manual addition:

  456
+  77
-----
  533

Example 3:

num1 = "0"
num2 = "0"

The answer is:

"0"

First Thought: Convert to Integer

The easiest code would be:

return str(int(num1) + int(num2))

But this violates the rule.

The problem is designed to handle very large numbers stored as strings. We must add digits ourselves.

Key Insight

Addition works from right to left.

At each position, we add:

digit_from_num1 + digit_from_num2 + carry

Then:

result_digit = total % 10
carry = total // 10

For example:

9 + 7 + 0 = 16

The current result digit is:

6

and the carry is:

1

We repeat this until both strings are fully processed and there is no carry left.

Algorithm

Use two pointers:

Initialize:

i = len(num1) - 1
j = len(num2) - 1
carry = 0
result = []

Then repeat while either string has digits left or carry remains:

1. Read the current digit from num1, or use 0 if i is out of bounds.
2. Read the current digit from num2, or use 0 if j is out of bounds.
3. Add both digits and carry.
4. Append the ones digit to result.
5. Update carry.
6. Move both pointers left.

At the end, reverse result and join it into a string.

Correctness

The algorithm simulates standard decimal addition column by column from right to left.

At each step, it computes the exact sum of the two digits at the current decimal place plus the carry from the previous lower place.

The expression:

total % 10

gives the digit that belongs in the current place.

The expression:

total // 10

gives the carry that must be added to the next higher place.

If one string is shorter, the algorithm treats its missing digits as 0, which is exactly how manual addition aligns numbers by their rightmost digits.

The loop continues while there are unprocessed digits or a remaining carry, so no digit or final carry is lost.

Because the result digits are produced from least significant to most significant, reversing them gives the correct final order.

Therefore, the returned string is the exact sum of num1 and num2.

Complexity

Here:

Ignoring the returned output string, the extra working space is O(1) besides the result buffer.

Implementation

from typing import List

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i = len(num1) - 1
        j = len(num2) - 1
        carry = 0
        result = []

        while i >= 0 or j >= 0 or carry:
            digit1 = ord(num1[i]) - ord("0") if i >= 0 else 0
            digit2 = ord(num2[j]) - ord("0") if j >= 0 else 0

            total = digit1 + digit2 + carry

            result.append(str(total % 10))
            carry = total // 10

            i -= 1
            j -= 1

        return "".join(reversed(result))

Code Explanation

We start from the last digit of each string:

i = len(num1) - 1
j = len(num2) - 1

The carry starts at zero:

carry = 0

The result list stores digits in reverse order:

result = []

The loop continues as long as there is something left to add:

while i >= 0 or j >= 0 or carry:

We convert one digit character into its numeric value:

ord(num1[i]) - ord("0")

This avoids converting the whole string into an integer.

If the pointer is already out of bounds, we use 0:

digit1 = ord(num1[i]) - ord("0") if i >= 0 else 0

Then we add the two digits and the carry:

total = digit1 + digit2 + carry

The current output digit is:

total % 10

The carry for the next column is:

total // 10

After processing this column, both pointers move left:

i -= 1
j -= 1

Finally, we reverse the collected digits:

return "".join(reversed(result))

Testing

def test_add_strings():
    s = Solution()

    assert s.addStrings("11", "123") == "134"
    assert s.addStrings("456", "77") == "533"
    assert s.addStrings("0", "0") == "0"
    assert s.addStrings("9", "1") == "10"
    assert s.addStrings("999", "1") == "1000"
    assert s.addStrings("1", "9999") == "10000"
    assert s.addStrings("123456789", "987654321") == "1111111110"

    print("all tests passed")

Test Notes