Domain 1EasyCORE

Add Strings

The problem requires adding two non-negative integers represented as strings and returning their sum also as a string. The inputs are `num1` and `num2`, which are strings of digits. The output should be the sum of these numbers in string format. The constraints specify that the length of each input string is between 1 and 10,000 characters, and they consist only of digits. There are no leading zeros except for the number zero itself.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

415. Add Strings

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 48.5%


Problem Breakdown

The problem requires adding two non-negative integers represented as strings and returning their sum also as a string. The inputs are num1 and num2, which are strings of digits. The output should be the sum of these numbers in string format. The constraints specify that the length of each input string is between 1 and 10,000 characters, and they consist only of digits. There are no leading zeros except for the number zero itself.

Intuition

A brute-force approach would involve converting the strings to integers, performing the addition, and then converting the result back to a string. However, this approach is not allowed by the follow-up constraint, which prohibits using built-in BigInteger libraries or directly converting the inputs to integers.

The key insight is to simulate the manual addition process that we perform with pen and paper. This involves iterating through the strings from right to left (least significant digit to most significant), adding corresponding digits along with any carry from the previous step, and constructing the result string accordingly.

Approach

  1. Initialize an empty list result to store the digits of the sum.
  2. Use two pointers, i and j, initialized to the last indices of num1 and num2, respectively.
  3. Initialize a variable carry to 0 to keep track of any carry-over during addition.
  4. Iterate while either pointer is non-negative or there is a carry:
    • Extract the current digit from num1 if i is non-negative, otherwise use 0.
    • Extract the current digit from num2 if j is non-negative, otherwise use 0.
    • Compute the sum of the two digits and the carry.
    • Append the last digit of the sum to the result.
    • Update the carry to be the quotient when the sum is divided by 10.
    • Decrement both pointers if they are non-negative.
  5. After the loop, reverse the result list to get the correct order and join it into a string.

Complexity Analysis

  • Time Complexity: O(max(len(num1), len(num2))), where we iterate through each digit of the longer number once.
  • Space Complexity: O(max(len(num1), len(num2))) for storing the result, plus O(1) additional space for variables.

Solution

def addStrings(num1: str, num2: str) -> str:
    result = []
    i, j = len(num1) - 1, len(num2) - 1
    carry = 0
    
    while i >= 0 or j >= 0 or carry > 0:
        digit1 = int(num1[i]) if i >= 0 else 0
        digit2 = int(num2[j]) if j >= 0 else 0
        total = digit1 + digit2 + carry
        result.append(str(total % 10))
        carry = total // 10
        i -= 1
        j -= 1
    
    return ''.join(result[::-1])

Edge Cases Handled

  • Empty Strings: Although the problem constraints prevent empty strings, the code handles cases where one or both strings are “0”.
  • Different Lengths: The code correctly handles cases where num1 and num2 have different lengths.
  • Carry Over: The code properly manages carry-over when the sum of two digits exceeds 9.
  • Leading Zeros: The result does not have leading zeros unless the sum is zero itself.