415. Add Strings

415. Add Strings (Easy)

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Companies:
Facebook, Microsoft

Related Topics:
Math

Similar Questions:

• Add Two Numbers (Medium)
• Multiply Strings (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/add-strings/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(1)
class Solution {
public:
    string addStrings(string num1, string num2) {
        string sum;
        int carry = 0;
        auto i1 = num1.rbegin(), i2 = num2.rbegin();
        while (i1 != num1.rend() || i2 != num2.rend() || carry) {
            int n = carry;
            if (i1 != num1.rend()) n += *i1++ - '0';
            if (i2 != num2.rend()) n += *i2++ - '0';
            carry = n / 10;
            sum += (n % 10) + '0';
        }
        reverse(sum.begin(), sum.end());
        return sum;
    }
};