Code Implementation

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1) - 1, len(num2) - 1
        carry = 0
        res = []
        while i >= 0 or j >= 0 or carry:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            total = n1 + n2 + carry
            res.append(str(total % 10))
            carry = total // 10
            i -= 1
            j -= 1
        return ''.join(res[::-1])
      

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
        string res = "";
        while (i >= 0 || j >= 0 || carry) {
            int n1 = i >= 0 ? num1[i--] - '0' : 0;
            int n2 = j >= 0 ? num2[j--] - '0' : 0;
            int sum = n1 + n2 + carry;
            res.push_back(sum % 10 + '0');
            carry = sum / 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
      

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        StringBuilder res = new StringBuilder();
        while (i >= 0 || j >= 0 || carry != 0) {
            int n1 = i >= 0 ? num1.charAt(i--) - '0' : 0;
            int n2 = j >= 0 ? num2.charAt(j--) - '0' : 0;
            int sum = n1 + n2 + carry;
            res.append(sum % 10);
            carry = sum / 10;
        }
        return res.reverse().toString();
    }
}
      

var addStrings = function(num1, num2) {
    let i = num1.length - 1, j = num2.length - 1, carry = 0, res = [];
    while (i >= 0 || j >= 0 || carry) {
        let n1 = i >= 0 ? +num1[i--] : 0;
        let n2 = j >= 0 ? +num2[j--] : 0;
        let sum = n1 + n2 + carry;
        res.push(sum % 10);
        carry = Math.floor(sum / 10);
    }
    return res.reverse().join('');
};
      

Problem Description

The "Add Strings" problem asks you to add two non-negative integers, num1 and num2, where each integer is given as a non-empty string. You must return the sum as a string as well.

• You are not allowed to convert the entire input strings directly to integers or use built-in big integer libraries.
• Each input string consists only of digits and does not contain any non-digit characters.
• The input strings may be very large (hundreds or thousands of digits), so you cannot simply use standard integer types.
• There is always exactly one valid answer for each input.

Thought Process

At first glance, you might think of simply converting the input strings to integers, adding them, and converting the result back to a string. However, the problem explicitly forbids this approach because the numbers can be much larger than what an integer type can hold.

Instead, you need to mimic the process of addition as you would do by hand: add the digits from right to left, keeping track of any carry. This is similar to how you would add two numbers on paper, starting from the units place and carrying over any overflow to the next digit.

The challenge is to handle different string lengths and manage the carry correctly throughout the addition.

Solution Approach

• Step 1: Initialize pointers i and j at the end of num1 and num2 respectively. Also, initialize a variable carry to 0 and an empty result container (like a list or string builder).
• Step 2: Loop while either pointer is valid or there is a carry:
  • Get the current digit from num1 and num2 (if the pointer is valid), otherwise use 0.
  • Add the two digits and the carry together.
  • The new digit to append is (sum % 10), and update carry as sum // 10 (for Python/Java/C++) or Math.floor(sum / 10) (for JavaScript).
  • Move the pointers one step to the left.
• Step 3: After the loop, the result is built in reverse order, so reverse it before returning as the final answer.
• Why this works: This approach ensures we never exceed the limits of integer types, and we only process one digit at a time, just like manual addition.

Example Walkthrough

Let's walk through an example with num1 = "456" and num2 = "77".

• Initial State: i = 2 (points to '6'), j = 1 (points to '7'), carry = 0, result = []
• First Iteration:
  • num1[2] = 6, num2[1] = 7, carry = 0
  • sum = 6 + 7 + 0 = 13
  • append 3 (13 % 10), carry = 1 (13 // 10)
  • result = ['3']
• Second Iteration:
  • i = 1, j = 0
  • num1[1] = 5, num2[0] = 7, carry = 1
  • sum = 5 + 7 + 1 = 13
  • append 3, carry = 1
  • result = ['3', '3']
• Third Iteration:
  • i = 0, j = -1
  • num1[0] = 4, num2 is out of range (use 0), carry = 1
  • sum = 4 + 0 + 1 = 5
  • append 5, carry = 0
  • result = ['3', '3', '5']
• End: No more digits or carry. Reverse result to get "533".

Time and Space Complexity

• Brute-force Approach: If you tried to convert the strings to integers and add them, this would be O(N) in practice, but is not allowed and would fail for very large inputs.
• Optimized Approach (current solution):
  • Time Complexity: O(max(N, M)), where N and M are the lengths of num1 and num2. We process each digit once from right to left.
  • Space Complexity: O(max(N, M)), since we store the result digits in a list or string builder before reversing.

Summary

The "Add Strings" problem is a classic example of simulating arithmetic operations on large numbers using string manipulation. By processing the digits from right to left and handling the carry at each step, we can add numbers of arbitrary length without worrying about integer overflow. The solution is efficient, easy to understand, and closely mimics manual addition, making it both practical and elegant.