# Add Strings
**Difficulty:** EASY
[External](https://leetcode.com/problems/add-strings)
Canonical: https://scaleengineer.com/dsa/problems/add-strings
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Avito](https://scaleengineer.com/companies/avito), [Capital One](https://scaleengineer.com/companies/capital-one), [Wayfair](https://scaleengineer.com/companies/wayfair), [Jane Street](https://scaleengineer.com/companies/jane-street)
---
## 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.

**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.

# Approaches
## Simulation with Inefficient String Concatenation
This method mimics the way humans add numbers on paper, starting from the least significant digit (the rightmost one). It iteratively calculates the sum of digits at each position, manages a carry-over, and builds the result string. However, it uses an inefficient way to build the string by prepending digits, which degrades performance significantly.
**Time:** `O(max(N, M)^2)`, where `N` and `M` are the lengths of `num1` and `num2`. Prepending a character to a string of length `k` takes `O(k)` time. Since this is done in a loop `max(N, M)` times, the total time complexity becomes quadratic. · **Space:** `O(max(N, M)^2)`. In each iteration, a new string is created for the result. The sum of the lengths of all these intermediate strings is `1 + 2 + ... + max(N, M)`, which results in quadratic space complexity.
**Pros:** The logic is very straightforward and easy to understand as it directly simulates manual addition.
**Cons:** Extremely inefficient for long input strings due to quadratic time and space complexity from repeated string concatenations.; Will likely result in a "Time Limit Exceeded" or "Memory Limit Exceeded" error on platforms with strict constraints.
### Explanation
The algorithm proceeds as follows:
*   Initialize two pointers, `i` and `j`, to point to the last character of `num1` and `num2`, respectively.
*   Initialize a `carry` variable to `0`.
*   Initialize an empty string, `result`, to store the sum.
*   Loop as long as `i` or `j` are valid indices, or if there is a `carry` left over.
*   Inside the loop:
    *   Get the integer value of the digit from `num1` at index `i`. If `i` is out of bounds, use `0`.
    *   Get the integer value of the digit from `num2` at index `j`. If `j` is out of bounds, use `0`.
    *   Calculate the `currentSum = digit1 + digit2 + carry`.
    *   The new `carry` for the next iteration is `currentSum / 10`.
    *   The digit for the current position is `currentSum % 10`.
    *   Prepend this digit to the `result` string. In Java, `result = (currentSum % 10) + result;`. This is an `O(L)` operation where `L` is the current length of `result`, as strings are immutable.
    *   Decrement `i` and `j` to move to the next digits to the left.
*   After the loop, `result` holds the final sum. A special case is if both input strings are "0", the result should be "0". The algorithm handles this correctly.
```java
class Solution {
    public String addStrings(String num1, String num2) {
        String result = "";
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;

        while (i >= 0 || j >= 0 || carry > 0) {
            int digit1 = (i >= 0) ? num1.charAt(i) - '0' : 0;
            int digit2 = (j >= 0) ? num2.charAt(j) - '0' : 0;

            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            int currentDigit = sum % 10;

            // Inefficient string concatenation
            result = currentDigit + result;

            i--;
            j--;
        }

        return result;
    }
}
```
### Algorithm
*   Initialize `result = ""`, `i = num1.length() - 1`, `j = num2.length() - 1`, `carry = 0`.
*   Loop while `i >= 0` or `j >= 0` or `carry > 0`.
*   Extract `digit1` from `num1` at `i` (or 0 if `i < 0`).
*   Extract `digit2` from `num2` at `j` (or 0 if `j < 0`).
*   Calculate `sum = digit1 + digit2 + carry`.
*   Update `carry = sum / 10`.
*   Prepend `sum % 10` to the `result` string.
*   Decrement `i` and `j`.
*   Return `result`.

## Simulation with StringBuilder
This approach also simulates manual, right-to-left addition but uses a `StringBuilder` for efficient string construction. By appending digits to a `StringBuilder` and reversing it once at the end, we avoid the costly re-creation of strings in a loop.
**Time:** `O(max(N, M))`, where `N` and `M` are the lengths of `num1` and `num2`. The algorithm iterates through the digits of the strings once. Appending to a `StringBuilder` is amortized `O(1)`, and the final reversal takes `O(max(N, M))` time. · **Space:** `O(max(N, M))`. The `StringBuilder` used to store the result will have a length of at most `max(N, M) + 1`.
**Pros:** Optimal time and space complexity for this problem.; Efficiently handles very large numbers within the given constraints.; The logic is still relatively simple and follows the natural process of addition.
**Cons:** Requires an extra step to reverse the string at the end, which adds a small constant factor overhead but doesn't change the overall complexity.
### Explanation
This method is an optimized version of the previous one. The core idea of simulating grade-school addition remains the same.
*   Initialize a `StringBuilder` to build the result string.
*   Initialize pointers `i` and `j` to the last characters of `num1` and `num2`.
*   Initialize `carry` to `0`.
*   Loop as long as there are digits in either `num1` or `num2` to process, or if a `carry` exists.
*   Inside the loop:
    *   Get the integer values of the digits from `num1` and `num2` at the current pointers. If a pointer is out of bounds, its corresponding digit is `0`.
    *   Calculate `sum = digit1 + digit2 + carry`.
    *   The digit for the current position is `sum % 10`. Append this to the `StringBuilder`. Appending to a `StringBuilder` is an amortized `O(1)` operation.
    *   The new `carry` for the next position is `sum / 10`.
    *   Decrement the pointers `i` and `j`.
*   After the loop, the `StringBuilder` contains the digits of the sum, but in reverse order (from least significant to most significant).
*   Reverse the `StringBuilder` and convert it to a string to get the final correct result.
```java
class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;

        while (i >= 0 || j >= 0 || carry > 0) {
            int digit1 = (i >= 0) ? num1.charAt(i--) - '0' : 0;
            int digit2 = (j >= 0) ? num2.charAt(j--) - '0' : 0;

            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            result.append(sum % 10);
        }

        return result.reverse().toString();
    }
}
```
### Algorithm
*   Initialize `StringBuilder result`, `i = num1.length() - 1`, `j = num2.length() - 1`, `carry = 0`.
*   Loop while `i >= 0` or `j >= 0` or `carry > 0`.
*   Extract `digit1` from `num1` at `i` (or 0 if `i < 0`) and decrement `i`.
*   Extract `digit2` from `num2` at `j` (or 0 if `j < 0`) and decrement `j`.
*   Calculate `sum = digit1 + digit2 + carry`.
*   Append `sum % 10` to the `result` StringBuilder.
*   Update `carry = sum / 10`.
*   After the loop, reverse the `result` StringBuilder.
*   Return the string representation of the reversed `result`.

# Solutions
### Java

```java
class Solution {
public
  String addStrings(String num1, String num2) {
    int i = num1.length() - 1, j = num2.length() - 1;
    StringBuilder ans = new StringBuilder();
    for (int c = 0; i >= 0 || j >= 0 || c > 0; --i, --j) {
      int a = i < 0 ? 0 : num1.charAt(i) - '0';
      int b = j < 0 ? 0 : num2.charAt(j) - '0';
      c += a + b;
      ans.append(c % 10);
      c /= 10;
    }
    return ans.reverse().toString();
  }
public
  String subStrings(String num1, String num2) {
    int m = num1.length(), n = num2.length();
    boolean neg = m < n || (m == n && num1.compareTo(num2) < 0);
    if (neg) {
      String t = num1;
      num1 = num2;
      num2 = t;
    }
    int i = num1.length() - 1, j = num2.length() - 1;
    StringBuilder ans = new StringBuilder();
    for (int c = 0; i >= 0; --i, --j) {
      c = (num1.charAt(i) - '0') - c - (j < 0 ? 0 : num2.charAt(j) - '0');
      ans.append((c + 10) % 10);
      c = c < 0 ? 1 : 0;
    }
    while (ans.length() > 1 && ans.charAt(ans.length() - 1) == '0') {
      ans.deleteCharAt(ans.length() - 1);
    }
    if (neg) {
      ans.append('-');
    }
    return ans.reverse().toString();
  }
}

```

### JavaScript

```javascript
/** * @param {string} num1 * @param {string} num2 * @return {string} */ var addStrings =
  function (num1, num2) {
    let i = num1.length - 1;
    let j = num2.length - 1;
    const ans = [];
    for (let c = 0; i >= 0 || j >= 0 || c; --i, --j) {
      c += i < 0 ? 0 : +num1[i];
      c += j < 0 ? 0 : +num2[j];
      ans.push(c % 10);
      c = Math.floor(c / 10);
    }
    return ans.reverse().join("");
  };
/** * @param {string} num1 * @param {string} num2 * @return {string} */ var subStrings =
  function (num1, num2) {
    const m = num1.length;
    const n = num2.length;
    const neg = m < n || (m == n && num1 < num2);
    if (neg) {
      const t = num1;
      num1 = num2;
      num2 = t;
    }
    let i = num1.length - 1;
    let j = num2.length - 1;
    const ans = [];
    for (let c = 0; i >= 0; --i, --j) {
      c = +num1[i] - c;
      if (j >= 0) {
        c -= +num2[j];
      }
      ans.push((c + 10) % 10);
      c = c < 0 ? 1 : 0;
    }
    while (ans.length > 1 && ans.at(-1) === 0) {
      ans.pop();
    }
    return (neg ? " - " : "") + ans.reverse().join("");
  };

```

### CPP

```cpp
class Solution {
public:
  string addStrings(string num1, string num2) {
    int i = num1.size() - 1, j = num2.size() - 1;
    string ans;
    for (int c = 0; i >= 0 || j >= 0 || c; --i, --j) {
      int a = i < 0 ? 0 : num1[i] - '0';
      int b = j < 0 ? 0 : num2[j] - '0';
      c += a + b;
      ans += to_string(c % 10);
      c /= 10;
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
  string subStrings(string num1, string num2) {
    int m = num1.size(), n = num2.size();
    bool neg = m < n || (m == n && num1 < num2);
    if (neg) {
      swap(num1, num2);
    }
    int i = num1.size() - 1, j = num2.size() - 1;
    string ans;
    for (int c = 0; i >= 0; --i, --j) {
      c = (num1[i] - '0') - c - (j < 0 ? 0 : num2[j] - '0');
      ans += to_string((c + 10) % 10);
      c = c < 0 ? 1 : 0;
    }
    while (ans.size() > 1 && ans.back() == '0') {
      ans.pop_back();
    }
    if (neg) {
      ans.push_back('-');
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def addStrings(self, num1: str, num2: str) -> str: i, j = len(num1) - 1, len(num2) - 1 ans = [] c = 0 while i >= 0 or j >= 0 or c: a = 0 if i < 0 else int(num1[i]) b = 0 if j < 0 else int(num2[j]) c, v = divmod(a + b + c, 10)  # nice ans . append ( str ( v )) i , j = i - 1 , j - 1 return "" . join ( ans [:: - 1 ]) # follow-up, substract def subStrings ( self , num1 : str , num2 : str ) -> str : m , n = len ( num1 ), len ( num2 ) neg = m < n or ( m == n and num1 < num2 ) if neg : num1 , num2 = num2 , num1 i , j = len ( num1 ) - 1 , len ( num2 ) - 1 ans = [] c = 0 while i >= 0 : c = int ( num1 [ i ]) - c - ( 0 if j < 0 else int ( num2 [ j ])) ans . append ( str (( c + 10 ) % 10 )) c = 1 if c < 0 else 0 i , j = i - 1 , j - 1 # eg. 99199 - 99198 = 1, ans here is "10000" while len ( ans ) > 1 and ans [ - 1 ] == "0" : ans . pop () if neg : # will not be "-0", neg only when <0 ans . append ( "-" ) return "" . join ( ans [:: - 1 ]) ############ class Solution : def addStrings ( self , num1 : str , num2 : str ) -> str : i , j = len ( num1 ) - 1 , len ( num2 ) - 1 ans = [] c = 0 while i >= 0 or j >= 0 or c : a = 0 if i < 0 else int ( num1 [ i ]) b = 0 if j < 0 else int ( num2 [ j ]) c , v = divmod ( a + b + c , 10 ) ans . append ( str ( v )) i , j = i - 1 , j - 1 return "" . join ( ans [:: - 1 ]) def subStrings ( self , num1 : str , num2 : str ) -> str : m , n = len ( num1 ), len ( num2 ) neg = m < n or ( m == n and num1 < num2 ) if neg : num1 , num2 = num2 , num1 i , j = len ( num1 ) - 1 , len ( num2 ) - 1 ans = [] c = 0 while i >= 0 : c = int ( num1 [ i ]) - c - ( 0 if j < 0 else int ( num2 [ j ])) ans . append ( str (( c + 10 ) % 10 )) c = 1 if c < 0 else 0 i , j = i - 1 , j - 1 while len ( ans ) > 1 and ans [ - 1 ] == "0" : ans . pop () if neg : ans . append ( "-" ) return "" . join ( ans [:: - 1 ])

```