Add Strings

Problem

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.

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.

Solution

The problem Add Strings can be solved using two pointers to add the last unprocessed digit from each strings along with the carry bit.

Implementation

class Solution
{
  public:
    string addStrings(string num1, string num2)
    {
        string ret;
        int idx1 = num1.size() - 1;
        int idx2 = num2.size() - 1;

        char carry = 0;
        while (idx1 >= 0 || idx2 >= 0)
        {
            carry += idx1 >= 0 ? num1[idx1--] - '0' : 0;
            carry += idx2 >= 0 ? num2[idx2--] - '0' : 0;

            ret += '0' + carry % 10;
            carry /= 10;
        }
        if (carry)
            ret += '1';

        reverse(ret.begin(), ret.end());
        return ret;
    }
};