415. Add Strings - Detailed Explanation

Problem Statement

You are given two non-negative integers represented as strings, num1 and num2. Your task is to return the sum of num1 and num2 as a string. You must solve the problem without converting the inputs directly into integers (i.e. using arithmetic operations on the strings themselves).

Example Inputs & Outputs

• Example 1:

  • Input: num1 = "11", num2 = "123"
  • Output: "134"
  • Explanation:
    The sum is computed as 11 + 123 = 134.

• Example 2:

  • Input: num1 = "456", num2 = "77"
  • Output: "533"
  • Explanation:
    The sum is computed as 456 + 77 = 533.

• Example 3:

  • Input: num1 = "0", num2 = "0"
  • Output: "0"
  • Explanation:
    The sum is 0 + 0 = 0.

Constraints

• Both num1 and num2 contain only digits.
• Both num1 and num2 do not have any leading zeros, except for the number 0 itself.
• The lengths of num1 and num2 are at least 1.

Hints

1. Process from Right to Left:
   Since addition is performed from the least significant digit (rightmost) to the most significant digit (leftmost), consider using two pointers starting at the end of both strings.

2. Maintain a Carry:
   Keep track of a carry value that may result from adding two digits. The carry will be added to the sum of the next pair of digits.

3. Build the Result:
   As you calculate each digit of the result, append it to a result container (or use a data structure that allows you to easily reverse the result later) because you’re processing the digits in reverse order.

4. Edge Cases:
   Handle cases where the two strings have different lengths, and remember to include the final carry (if non-zero) after processing all digits.

Approach 1: Digit-by-Digit Addition (Simulation)

Step-by-Step Walkthrough

1. Initialize Pointers and Variables:

   • Set two pointers, i and j, to point to the last characters of num1 and num2 respectively.
   • Initialize a variable carry to 0.
   • Prepare an empty list or string builder to accumulate result digits.

2. Iterate Through Both Strings:

   • While either pointer is valid or there is a non-zero carry:
     • Extract the current digit from num1 if available; otherwise, treat it as 0.
     • Extract the current digit from num2 if available; otherwise, treat it as 0.
     • Calculate the sum: digit1 + digit2 + carry.
     • Update the current digit of the result as the remainder of the sum when divided by 10 (i.e. sum % 10).
     • Update carry as the quotient of the sum divided by 10 (i.e. sum // 10).
     • Move the pointers one position to the left.

3. Reverse and Return the Result:

   • Since digits are collected from least significant to most significant, reverse the result and join it into a string.
   • Return the resulting string.

Visual Example Using num1 = "456", num2 = "77"

• Initialize:
  i = 2 (pointing at '6'), j = 1 (pointing at '7'), carry = 0, result = [].

• Iteration 1:

  • Digits: '6' (from num1) and '7' (from num2) → 6 + 7 + 0 = 13.
  • Current Digit: 13 % 10 = 3, carry = 13 // 10 = 1.
  • Result: ["3"].
  • Move pointers: i = 1, j = 0.

• Iteration 2:

  • Digits: '5' (from num1) and '7' (from num2) → 5 + 7 + 1 = 13.
  • Current Digit: 13 % 10 = 3, carry = 1.
  • Result: ["3", "3"].
  • Move pointers: i = 0, j = -1.

• Iteration 3:

  • Digits: '4' (from num1) and no digit from num2 (use 0) → 4 + 0 + 1 = 5.
  • Current Digit: 5 % 10 = 5, carry = 0.
  • Result: ["3", "3", "5"].
  • Move pointers: i = -1, j = -1.

• Finalize:
  Reverse the result → "5", "3", "3" → join to form "533".

Approach 2: Using a String Builder (Java-Style Simulation)

The idea remains the same as in Approach 1, but you can leverage a mutable string builder (or similar data structure) to efficiently append digits and then reverse the final string.

Code Examples

Python Code