Scale Engineer

Add Strings

Easy
#0402Time: `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.5 companies
Patterns
Math
Data structures
String
Companies
AirbnbAvitoCapital OneWayfair

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.
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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem