Add Strings
Easy · Math & Geometry · Explanation and code example
Digit Addition with Carry
How it works
Simulate column addition from the rightmost digits. Add the available digit from each string and the previous carry, emit the remainder modulo ten, then carry the quotient. Reverse the collected digits at the end.
Steps
- Start at both strings’ last indices with carry zero.
- Emit one result digit while either input or carry remains.
- Reverse the digits and join them.
Complexity
- Time: O(max(n, m)).
- Space: O(max(n, m)) for output construction.
Things to watch for
- Continue when a final carry remains.
- Treat an exhausted input as a zero digit.
- Avoid converting the whole strings to integers.
Python code example
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
ans = []
carry = 0
i = len(num1) - 1
j = len(num2) - 1
while i >= 0 or j >= 0 or carry:
if i >= 0:
carry += int(num1[i])
if j >= 0:
carry += int(num2[j])
ans.append(str(carry % 10))
carry //= 10
i -= 1
j -= 1
return ''.join(reversed(ans))
C++ code example
class Solution {
public:
string addStrings(string num1, string num2) {
string ans;
int carry = 0;
int i = num1.length() - 1;
int j = num2.length() - 1;
while (i >= 0 || j >= 0 || carry) {
if (i >= 0)
carry += num1[i--] - '0';
if (j >= 0)
carry += num2[j--] - '0';
ans += carry % 10 + '0';
carry /= 10;
}
ranges::reverse(ans);
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.