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 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

 

Example 1:

Input: num1 = "11", num2 = "123"
Output: "134"

Example 2:

Input: num1 = "456", num2 = "77"
Output: "533"

Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"

 

Constraints:

• 1 <= num1.length, num2.length <= 104
• num1 and num2 consist of only digits.
• num1 and num2 don't have any leading zeros except for the zero itself.

Companies:
Facebook, Adobe, Microsoft, Google, Amazon, Oracle, Wayfair

Related Topics:
Math, String, Simulation

Similar Questions:

• Add Two Numbers (Medium)
• Multiply Strings (Medium)
• Add to Array-Form of Integer (Easy)

Solution 1.

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

Or

// OJ: https://leetcode.com/problems/add-strings/
// Author: github.com/lzl124631x
// Time: O(M + N)
// Space: O(1)
class Solution {
public:
    string addStrings(string a, string b) {
        reverse(begin(a), end(a));
        reverse(begin(b), end(b));
        int carry = 0;
        string ans;
        for (int i = 0; i < a.size() || i < b.size() || carry; ++i) {
            if (i < a.size()) carry += a[i] - '0';
            if (i < b.size()) carry += b[i] - '0';
            ans.push_back('0' + carry % 10);
            carry /= 10;
        }
        reverse(begin(ans), end(ans));
        return ans;
    }
};