Add Strings

LeetCode 415: Add Strings Solution & Explanation

Problem Overview

TL;DR: The optimal solution simulates elementary school column addition digit-by-digit from right to left, managing a carry value and handling strings of unequal lengths by treating missing digits as zero.

The problem asks us to compute the sum of two non-negative integers, num1 and num2, which are provided as strings. We must return the result as a string. The constraints explicitly forbid using built-in libraries for handling large integers (like BigInteger in Java) or converting the inputs directly to integers. This makes LeetCode 415 a classic test of implementation skills and understanding of arithmetic simulation.

Brute Force Approach for Add Strings

A naive approach would be to parse the string inputs into standard integer types, perform the addition, and convert the result back to a string.

Pseudo-code:

function addStrings(num1, num2):
    int_val1 = parseToInt(num1)
    int_val2 = parseToInt(num2)
    sum_val = int_val1 + int_val2
    return toString(sum_val)

Why it fails: This approach fails due to Integer Overflow. The problem constraints state that the length of num1 and num2 can be up to 10,000 characters. A standard 64-bit integer (like long long in C++ or long in Java) can only store values up to approximately 19 digits ($2^{63}-1$). A number with 10,000 digits vastly exceeds the storage capacity of standard CPU registers. Therefore, this approach will crash or produce incorrect results for large inputs, which is the primary challenge of the Add Strings problem.

Algorithm Strategy: String Manipulation Patterns

To implement the String - Multiply Strings/Add Strings (Manual Simulation) pattern:

1. Pointer Initialization: Initialize two pointers, i and j, pointing to the last character of num1 and num2 respectively.
2. State Maintenance: Maintain a carry variable, initialized to 0, to store the overflow from the sum of the previous position.
3. Iterative Processing: Loop as long as there are digits left to process in either string (i >= 0 or j >= 0) OR there is a remaining carry (carry != 0).
4. Digit Extraction: Inside the loop, get the digit at num1[i] and num2[j]. If a pointer is out of bounds (less than 0), treat the digit as 0.
5. ASCII Conversion: Convert the character digits to integer values by subtracting the ASCII value of '0'.
6. Computation: Calculate the sum of the two digits plus the carry.
   • Append sum % 10 to the result builder.
   • Update carry to sum / 10.
7. Result Formatting: Since we append digits from the least significant to the most significant, the result string is currently backwards. Reverse the string to obtain the final correct sum.

Execution Flow

Let's trace num1 = "456" and num2 = "77".

1. Start: i points to '6' (index 2), j points to '7' (index 1), carry = 0. Result buffer is empty.
2. Iteration 1:
   • val1 = 6, val2 = 7.
   • sum = 6 + 7 + 0 = 13.
   • Append 3 (13 % 10) to buffer. Buffer: "3".
   • carry = 1 (13 / 10).
   • Decrement i (now index 1), decrement j (now index 0).
3. Iteration 2:
   • val1 = 5, val2 = 7.
   • sum = 5 + 7 + 1 (carry) = 13.
   • Append 3 to buffer. Buffer: "33".
   • carry = 1.
   • Decrement i (now index 0), decrement j (now index -1).
4. Iteration 3:
   • val1 = 4, val2 = 0 (since j < 0).
   • sum = 4 + 0 + 1 (carry) = 5.
   • Append 5 to buffer. Buffer: "335".
   • carry = 0.
   • Decrement i (now index -1), decrement j (now index -2).
5. Termination: i < 0, j < 0, and carry == 0. Loop ends.
6. Finalize: Reverse "335" to get "533".

Proof of Correctness

The algorithm is correct by induction.

• Base Case: For single-digit numbers, the sum d1 + d2 produces a correct digit (d1+d2)%10 and a correct carry (d1+d2)/10.
• Inductive Step: Assume the addition is correct for the first $k$ positions (from the right). At position $k+1$, we add the digits from num1 and num2 along with the carry generated by position $k$. This aligns strictly with the definition of positional notation arithmetic.
• Termination: The loop condition ensures we process every digit of the longer string and any remaining carry (e.g., $50 + 50 = 100$, where the '1' comes from the final carry). Thus, no value is lost.

Pattern Reuse Notes

The manual simulation pattern used in LeetCode 415 is a fundamental technique for string-based arithmetic.

• LeetCode 43: Multiply Strings: This problem extends the addition logic. You simulate column multiplication, which involves multiplying digits and adding the intermediate results (using the logic from Add Strings).
• LeetCode 67: Add Binary: This is virtually identical to Add Strings, but in base-2. The logic remains sum % 2 and carry / 2.

Mastering this pattern ensures you can handle arbitrary-precision arithmetic problems in technical interviews.

Reference Implementation

C++ Solution for LeetCode 415

1#include <string>
2#include <algorithm>
3#include <vector>
4
5class Solution {
6public:
7    string addStrings(string num1, string num2) {
8        string result = "";
9        int i = num1.length() - 1;
10        int j = num2.length() - 1;
11        int carry = 0;
12        
13        // Reserve space to avoid multiple reallocations
14        result.reserve(std::max(num1.length(), num2.length()) + 1);
15
16        while (i >= 0 || j >= 0 || carry > 0) {
17            // Extract digits or use 0 if pointer is out of bounds
18            int d1 = (i >= 0) ? num1[i] - '0' : 0;
19            int d2 = (j >= 0) ? num2[j] - '0' : 0;
20            
21            int sum = d1 + d2 + carry;
22            
23            // Append the unit digit of sum
24            result.push_back((sum % 10) + '0');
25            
26            // Update carry
27            carry = sum / 10;
28            
29            i--;
30            j--;
31        }
32        
33        // The result is currently backwards, so reverse it
34        reverse(result.begin(), result.end());
35        return result;
36    }
37};

Java Solution for LeetCode 415

1class Solution {
2    public String addStrings(String num1, String num2) {
3        StringBuilder sb = new StringBuilder();
4        
5        int i = num1.length() - 1;
6        int j = num2.length() - 1;
7        int carry = 0;
8        
9        while (i >= 0 || j >= 0 || carry > 0) {
10            // Get digit from num1 or 0 if exhausted
11            int d1 = (i >= 0) ? num1.charAt(i) - '0' : 0;
12            // Get digit from num2 or 0 if exhausted
13            int d2 = (j >= 0) ? num2.charAt(j) - '0' : 0;
14            
15            int sum = d1 + d2 + carry;
16            
17            // Append the least significant digit
18            sb.append(sum % 10);
19            
20            // Update carry for next position
21            carry = sum / 10;
22            
23            i--;
24            j--;
25        }
26        
27        // Reverse because we appended from right to left
28        return sb.reverse().toString();
29    }
30}

Python Solution for LeetCode 415

1class Solution:
2    def addStrings(self, num1: str, num2: str) -> str:
3        result = []
4        i, j = len(num1) - 1, len(num2) - 1
5        carry = 0
6        
7        # Loop until both strings are processed and carry is 0
8        while i >= 0 or j >= 0 or carry > 0:
9            # Convert char to int, use 0 if index out of bounds
10            d1 = int(num1[i]) if i >= 0 else 0
11            d2 = int(num2[j]) if j >= 0 else 0
12            
13            total_sum = d1 + d2 + carry
14            
15            # Append the unit digit
16            result.append(str(total_sum % 10))
17            
18            # Update carry
19            carry = total_sum // 10
20            
21            i -= 1
22            j -= 1
23            
24        # Join and reverse the list to get the final string
25        return "".join(result[::-1])