Solution
The problem is pretty straightforward and the best approach is to start traversing the strings from the end (least significant digit) and add the two numbers while keeping a track of carry.
Suppose we have two number strings, “123” and “999”. As a first step, we add 9 + 3 with a carry initially set to 0 then:
result = 2 ((9 + 3 + carry) % 10)
carry = 1 ((9 + 3 + carry) / 10)
These are general rules for base-n addition (just replace 10 with n).
string addStrings(string num1, string num2) {
string ans = "";
int carry = 0;
for (int i=num1.length()-1, j=num2.length()-1; i>=0 || j>=0; i--, j--) {
int n1 = i < 0 ? 0 : num1[i]-'0';
int n2 = j < 0 ? 0 : num2[j]-'0';
ans += (n1 + n2 + carry) % 10 + '0';
carry = (n1 + n2 + carry)/10;
}
if (carry)
ans += '1';
reverse(begin(ans), end(ans));
return ans;
}
Time complexity: O(max(n1, n2)) where n1 and n2 are the no. of digits in the given numbers (size of strings)