Add Strings
Schoolbook addition from the rightmost digit — carry through, prepend remaining carry at the end.
4 min read
math string
Problem#
Given two non-negative integers as strings, return their sum as a string. Don’t use built-in BigInteger / conversion to integer types.
Examples#
"11", "123"→"134"."456", "77"→"533";"0", "0"→"0".
Constraints#
1 <= num1.length, num2.length <= 10^4.
Approach#
Two pointers from the right. Add corresponding digits plus carry; push the units digit to the result; carry the tens digit. Reverse at the end.
Solution#
class Solution {public: string addStrings(string a, string b) { int i = a.size() - 1, j = b.size() - 1, carry = 0; string out; while (i >= 0 || j >= 0 || carry) { int x = (i >= 0) ? a[i--] - '0' : 0; int y = (j >= 0) ? b[j--] - '0' : 0; int s = x + y + carry; out.push_back('0' + s % 10); carry = s / 10; } reverse(out.begin(), out.end()); return out; }};func addStrings(a string, b string) string { i, j, carry := len(a)-1, len(b)-1, 0 out := []byte{} for i >= 0 || j >= 0 || carry > 0 { x, y := 0, 0 if i >= 0 { x = int(a[i] - '0') i-- } if j >= 0 { y = int(b[j] - '0') j-- } s := x + y + carry out = append(out, byte('0'+s%10)) carry = s / 10 } for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 { out[l], out[r] = out[r], out[l] } return string(out)}class Solution: def addStrings(self, num1: str, num2: str) -> str: i, j, carry = len(num1) - 1, len(num2) - 1, 0 out: list[str] = [] while i >= 0 or j >= 0 or carry: x = ord(num1[i]) - ord('0') if i >= 0 else 0 y = ord(num2[j]) - ord('0') if j >= 0 else 0 s = x + y + carry out.append(str(s % 10)) carry = s // 10 i -= 1 j -= 1 return ''.join(reversed(out))var addStrings = function(num1, num2) { let i = num1.length - 1, j = num2.length - 1, carry = 0; const out = []; while (i >= 0 || j >= 0 || carry) { const x = i >= 0 ? num1.charCodeAt(i--) - 48 : 0; const y = j >= 0 ? num2.charCodeAt(j--) - 48 : 0; const s = x + y + carry; out.push(String(s % 10)); carry = Math.floor(s / 10); } return out.reverse().join('');};class Solution { public String addStrings(String num1, String num2) { int i = num1.length() - 1, j = num2.length() - 1, carry = 0; StringBuilder out = new StringBuilder(); while (i >= 0 || j >= 0 || carry > 0) { int x = i >= 0 ? num1.charAt(i--) - '0' : 0; int y = j >= 0 ? num2.charAt(j--) - '0' : 0; int s = x + y + carry; out.append((char) ('0' + s % 10)); carry = s / 10; } return out.reverse().toString(); }}function addStrings(num1: string, num2: string): string { let i = num1.length - 1, j = num2.length - 1, carry = 0; const out: string[] = []; while (i >= 0 || j >= 0 || carry) { const x = i >= 0 ? num1.charCodeAt(i--) - 48 : 0; const y = j >= 0 ? num2.charCodeAt(j--) - 48 : 0; const s = x + y + carry; out.push(String(s % 10)); carry = Math.floor(s / 10); } return out.reverse().join('');}Editorial#
Single-loop short-circuit (i >= 0 || j >= 0 || carry) cleanly handles unequal lengths and a final carry-out. Pushing then reversing is O(n) total — cheaper than inserting at front each iteration.
Complexity#
- Time:
O(max(m, n)). - Space:
O(max(m, n)).
Concept revision#
Related#