Add Strings

Schoolbook addition from the rightmost digit — carry through, prepend remaining carry at the end.

Easy
Time O(max(m, n)) Space O(max(m, n))
LeetCode
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#

Add Strings
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.