Problem 415

Abstract / Summary

Add two numbers given as strings and return their sum as a string without using built in conversion functions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0415.py

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        l1 = len(num1)
        l2 = len(num2)
        if l1 < l2:
            num1 = ("0" * (l2 - l1)) + num1
            l1 = l2
        if l2 < l1:
            num2 = ("0" * (l1 - l2)) + num2

        carry = 0
        result = ""
        for i in range(l1 - 1, -1, -1):
            a = ord(num1[i]) - ord('0')
            b = ord(num2[i]) - ord('0')

            c = a + b + carry
            if c >= 10:
                carry = 1
                c -= 10
            else:
                carry = 0

            result += str(c)

        if carry == 1:
            result += "1"

        # building in reverse is faster than prepending single digits a thousand times
        return result[::-1]
30 lines | 799 bytes | submitted September 7, 2023 | GitHub   4% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 52% (1+ million submissions).

Typical patterns to solve this problem:
  • Math
  • Simulation
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The implementation provides a method to add two non-negative integer values that are supplied as decimal strings. It works without converting the whole strings to integer types, thereby avoiding overflow for very large numbers. The algorithm proceeds by first equalizing the lengths of the two input strings, then iterating from the least significant digit toward the most significant digit while maintaining a carry flag, and finally producing the summed string in the correct order.

Normalizing Input Lengths

To simplify the digit-wise addition loop, the code ensures that both strings have the same length. If num1 is shorter, it is left-padded with the appropriate number of '0' characters; the same is done for num2 when it is shorter. The length variables l1 and l2 are updated accordingly.

l1 = len(num1)
l2 = len(num2)
if l1 < l2:
    num1 = ("0" * (l2 - l1)) + num1
    l1 = l2
if l2 < l1:
    num2 = ("0" * (l1 - l2)) + num2

This step guarantees that the subsequent loop can index both strings at the same position without additional bounds checks.

Digitwise Addition Loop

The core of the algorithm iterates from the rightmost index (l1 - 1) down to 0. For each position, the characters are converted to their numeric values by subtracting the ASCII code of '0'. The sum of the two digits and any existing carry is computed, the new digit to store is derived, and the carry for the next iteration is updated.

carry = 0
result = ""
for i in range(l1 - 1, -1, -1):
    a = ord(num1[i]) - ord('0')
    b = ord(num2[i]) - ord('0')

    c = a + b + carry
    if c >= 10:
        carry = 1
        c -= 10
    else:
        carry = 0

    result += str(c)

The use of ord avoids the overhead of converting each character through higher-level functions, and the conditional adjustment of c keeps the digit within the range 0-9.

Final Carry Handling

After processing all digit positions, a remaining carry of 1 indicates that the sum has an extra most-significant digit. The code appends this digit to the result string.

if carry == 1:
    result += "1"

This branch correctly handles cases such as adding "999" and "1" where the result length exceeds the original operand lengths.

Result Construction

During the loop, digits are appended to result in reverse order (least significant first). Rather than inserting at the front of the string for each iteration-a costly operation-the algorithm builds the string backwards and performs a single reversal at the end. This approach reduces the number of memory reallocations and copies.

# building in reverse is faster than prepending single digits a thousand times
return result[::-1]

The slice notation [::-1] creates a reversed copy of the accumulated string, delivering the final sum in the correct most-significant-to-least-significant order.

Edge Cases Addressed

The code gracefully handles inputs of differing lengths by padding the shorter string with leading zeros, ensuring that the addition loop never encounters an index out of range. It also correctly processes the scenario where the final addition generates an extra carry, guaranteeing that the resulting string reflects the true magnitude of the sum. Leading zeros in the original inputs are preserved through the padding step, and the final reversal eliminates any artificial zeros that might have been introduced at the front of the intermediate result.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have two towers made of number blocks, but they are different heights. The first thing that happens is adding some invisible zero blocks to the shorter tower so that both towers are the exact same height. This makes it much easier to stack them up properly.

Now, picture starting at the very bottom blocks of both towers. You add those two blocks together, plus any extra bit that might have carried over from the step before. If that total is ten or more, you keep a little note called a carry to add to the next pair of blocks above. You write down the last digit of your sum and move up to the next pair. You keep doing this all the way to the top of the towers.

If there is still a carry note left over after the very top block, you place one final block on top of everything. Because all the work was done from the bottom to the top, the result is currently sitting upside down. Flipping it over shows the final total for these two big numbers.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.26 | σ = 1.07

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java JS Rust Python Go TS
LeetcodeHelp C++ Java Python
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
everthis JS
fartem Ruby
fpdjsns C++
haoel C++
JoshCrozier JS
keineahnung2345 C++
linouk23 C++
lkwq007 Python
qiyuangong Java
ruoru Rust
shreymehul C#
suxrobGM C#
varunu28 Java
vli02 C
yuanliu666 Kotlin
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fartem Ruby
fpdjsns C++
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
linouk23 C++
lkwq007 Python
qiyuangong Java
ruoru Rust
shreymehul C#
suxrobGM C#
varunu28 Java
vli02 C
yuanliu666 Kotlin
zfang399 C++
39 links | 24 authors | 11 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

29 easy 13 medium
43 solutions   September 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality