Problem Description

You are given two non-negative integers represented as strings, num1 and num2. Your task is to return the sum of these two numbers as a string.

The key constraints are:

• You cannot use any built-in library designed for handling large integers (like BigInteger in Java)
• You cannot directly convert the input strings to integers

This problem simulates manual addition that you would do on paper. You need to add the numbers digit by digit from right to left, keeping track of any carry values that occur when the sum of two digits exceeds 9.

For example:

• If num1 = "123" and num2 = "456", the output should be "579"
• If num1 = "99" and num2 = "1", the output should be "100" (note the carry propagation)

The solution implements this by:

1. Starting from the rightmost digits of both strings
2. Adding corresponding digits along with any carry from the previous position
3. Recording the result digit (sum % 10) and updating the carry (sum / 10)
4. Continuing until all digits are processed and there's no remaining carry
5. Building the result string in reverse order, then reversing it at the end

The provided code also includes a bonus subStrings method that performs string subtraction using similar digit-by-digit processing with borrowing instead of carrying.

Intuition

Think about how you learned to add numbers in elementary school. When adding two multi-digit numbers on paper, you start from the rightmost column (ones place) and work your way left. For each column, you add the digits and if the sum is 10 or greater, you write down the ones digit and carry the 1 to the next column.

Since we can't convert the strings to integers directly, we need to simulate this manual addition process character by character. The key insight is that we can extract individual digits from the strings using indexing and convert just single characters to integers (like int('5') gives us 5), which doesn't violate the constraint.

The challenge is handling strings of different lengths. When one number has more digits than the other, we essentially treat the missing digits as zeros. For instance, adding "999" and "1" is like adding "999" and "001".

We use two pointers starting from the end of each string because addition naturally flows from right to left due to the carry mechanism. The carry value c persists across iterations - if adding two digits gives us a sum ≥ 10, we need to remember to add that extra 1 to the next column.

The loop continues as long as:

• There are still digits to process in num1 (i >= 0)
• OR there are still digits to process in num2 (j >= 0)
• OR there's still a carry value to propagate (c > 0)

Building the answer in reverse (appending digits to a list then reversing at the end) is more efficient than prepending to a string, as string concatenation in Python creates new string objects each time.

The divmod(a + b + c, 10) operation elegantly gives us both the new carry (quotient) and the digit to record (remainder) in one step, which is exactly what we need for each position in our manual addition.

Solution Approach

The solution uses a two-pointer technique to traverse both strings from right to left, simulating manual addition with carry propagation.

Implementation Details:

1. Initialize pointers and variables:

   • Set i = len(num1) - 1 and j = len(num2) - 1 to point to the last digits of each string
   • Create an empty list ans to store result digits
   • Initialize carry c = 0

2. Main addition loop:

   while i >= 0 or j >= 0 or c:

   This loop continues while there are digits to process OR there's a carry to handle.

3. Extract digits safely:

   a = 0 if i < 0 else int(num1[i])
   b = 0 if j < 0 else int(num2[j])

   When one string runs out of digits, we treat missing positions as 0.

4. Calculate sum and update carry:

   c, v = divmod(a + b + c, 10)

   • v gets the remainder (digit to store: (a + b + c) % 10)
   • c gets the quotient (new carry: (a + b + c) // 10)

5. Store result and move pointers:

   ans.append(str(v))
   i, j = i - 1, j - 1

   Append the digit to our result list and move both pointers left.

6. Build final string:

   return "".join(ans[::-1])

   Since we built the answer backwards (from least to most significant digit), we reverse it before joining.

For the bonus subtraction method subStrings:

The subtraction follows similar logic but with key differences:

• First determines which number is larger to handle the sign of the result
• Uses borrowing instead of carrying: c = 1 if c < 0 else 0
• Calculates difference with borrowing: c = int(num1[i]) - c - int(num2[j])
• Adds 10 and takes modulo to handle negative differences: (c + 10) % 10
• Removes leading zeros from the result
• Adds negative sign if the first number was smaller

Time Complexity: O(max(m, n)) where m and n are the lengths of the input strings, as we traverse each string once.

Space Complexity: O(1) ignoring the output string, as we only use a constant amount of extra variables.

Example Walkthrough

Let's trace through adding num1 = "99" and num2 = "1" to see how the algorithm handles carry propagation.

Initial Setup:

• i = 1 (pointing to last '9' in "99")
• j = 0 (pointing to '1' in "1")
• c = 0 (no initial carry)
• ans = [] (empty result list)

Iteration 1: (rightmost column: 9 + 1)

• i = 1, j = 0, c = 0
• Extract digits: a = 9 (from num1[1]), b = 1 (from num2[0])
• Calculate: 9 + 1 + 0 = 10
• divmod(10, 10) gives us c = 1 (new carry), v = 0 (digit to store)
• Append '0' to ans: ans = ['0']
• Move pointers: i = 0, j = -1

Iteration 2: (middle column: 9 + 0 + carry)

• i = 0, j = -1, c = 1
• Extract digits: a = 9 (from num1[0]), b = 0 (j < 0, so use 0)
• Calculate: 9 + 0 + 1 = 10
• divmod(10, 10) gives us c = 1 (new carry), v = 0 (digit to store)
• Append '0' to ans: ans = ['0', '0']
• Move pointers: i = -1, j = -2

Iteration 3: (leftmost column: just the carry)

• i = -1, j = -2, c = 1
• Extract digits: a = 0 (i < 0, so use 0), b = 0 (j < 0, so use 0)
• Calculate: 0 + 0 + 1 = 1
• divmod(1, 10) gives us c = 0 (no more carry), v = 1 (digit to store)
• Append '1' to ans: ans = ['0', '0', '1']
• Move pointers: i = -2, j = -3

Loop exits because i < 0, j < 0, and c = 0

Final Step:

• Reverse and join: ans[::-1] = ['1', '0', '0']
• Return: "100"

The algorithm correctly handles the cascading carry, turning 99 + 1 into 100 by propagating the carry through multiple positions until it's fully resolved.

Solution Implementation

Time and Space Complexity

Time Complexity:

For addStrings: O(max(m, n)) where m is the length of num1 and n is the length of num2. The algorithm iterates through both strings once from right to left, processing each digit exactly once. The while loop runs for max(m, n) + 1 iterations in the worst case (when there's a final carry), and each iteration performs constant time operations including integer conversions, arithmetic operations, and string append.

For subStrings: O(max(m, n)) where m is the length of num1 and n is the length of num2. The algorithm first performs a comparison which takes O(min(m, n)) time in the worst case for string comparison. Then it iterates through the longer string once, performing constant time operations per digit. The final cleanup loop to remove leading zeros runs at most O(max(m, n)) times.

Space Complexity:

For addStrings: O(max(m, n)) for the ans list which stores the result digits. The result can have at most max(m, n) + 1 digits (when there's a carry from the most significant digit). The additional variables i, j, c, a, b, and v use O(1) space.

For subStrings: O(max(m, n)) for the ans list which stores the result digits. The result can have at most max(m, n) digits. The additional variables including neg, i, j, and c use O(1) space. Note that when swapping num1 and num2, no additional space is used as Python just swaps references.

Common Pitfalls

1. Forgetting to Handle the Final Carry

One of the most common mistakes is forgetting that after processing all digits, there might still be a carry that needs to be added to the result.

Incorrect Implementation:

def addStrings(self, num1: str, num2: str) -> str:
    i, j = len(num1) - 1, len(num2) - 1
    result = []
    carry = 0
  
    # Bug: Only loops while there are digits, ignores final carry
    while i >= 0 or j >= 0:  # Missing "or carry"
        digit1 = 0 if i < 0 else int(num1[i])
        digit2 = 0 if j < 0 else int(num2[j])
        carry, digit_sum = divmod(digit1 + digit2 + carry, 10)
        result.append(str(digit_sum))
        i -= 1
        j -= 1
  
    return "".join(result[::-1])

# This fails for cases like "99" + "1" 
# Expected: "100", but returns "00" (missing the final '1')

Solution: Always include or carry in the loop condition to ensure the final carry is processed.

2. Building the Result in the Wrong Order

Another frequent error is forgetting that when we process digits from right to left, we're building the result backwards and need to reverse it.

Incorrect Implementation:

def addStrings(self, num1: str, num2: str) -> str:
    i, j = len(num1) - 1, len(num2) - 1
    result = []
    carry = 0
  
    while i >= 0 or j >= 0 or carry:
        digit1 = 0 if i < 0 else int(num1[i])
        digit2 = 0 if j < 0 else int(num2[j])
        carry, digit_sum = divmod(digit1 + digit2 + carry, 10)
        result.append(str(digit_sum))
        i -= 1
        j -= 1
  
    # Bug: Forgot to reverse the result
    return "".join(result)  # Missing [::-1]

# For "123" + "456", this returns "975" instead of "579"

Solution: Always reverse the result list before joining, or alternatively, insert digits at the beginning of the result (though this is less efficient).

3. Incorrect Handling of Leading Zeros in Subtraction

When implementing subtraction, failing to remove leading zeros can produce incorrect-looking results.

Incorrect Implementation:

def subStrings(self, num1: str, num2: str) -> str:
    # ... (setup code)
  
    # Process subtraction...
    while i >= 0:
        # ... (subtraction logic)
        result.append(str((difference + 10) % 10))
        # ...
  
    # Bug: Forgot to remove leading zeros
    # If we subtract "100" - "99", we might get "001" instead of "1"
  
    if is_negative:
        result.append('-')
  
    return ''.join(result[::-1])

Solution: Always strip leading zeros after subtraction, but ensure at least one digit remains (for the case when the result is "0").

4. Confusing Carry Logic with Borrow Logic

When implementing both addition and subtraction, it's easy to mix up the carry/borrow update logic.

Incorrect Implementation:

def subStrings(self, num1: str, num2: str) -> str:
    # ...
    borrow = 0
  
    while i >= 0:
        digit1 = int(num1[i])
        digit2 = 0 if j < 0 else int(num2[j])
      
        difference = digit1 - borrow - digit2
      
        # Bug: Using addition carry logic for subtraction
        borrow, digit = divmod(difference, 10)  # Wrong!
        # This doesn't handle negative differences correctly
      
        result.append(str(digit))
        i -= 1
        j -= 1

Solution: For subtraction, explicitly check if the difference is negative and set borrow accordingly:

result.append(str((difference + 10) % 10))
borrow = 1 if difference < 0 else 0