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
- Initialize an empty list
resultto store the digits of the sum. - Use two pointers,
iandj, initialized to the last indices ofnum1andnum2, respectively. - Initialize a variable
carryto 0 to keep track of any carry-over during addition. - Iterate while either pointer is non-negative or there is a carry:
- Extract the current digit from
num1ifiis non-negative, otherwise use 0. - Extract the current digit from
num2ifjis 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.
- Extract the current digit from
- After the loop, reverse the
resultlist 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
num1andnum2have 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.