415. Add Strings

EasyMathStringSimulation
Leetcode Link

Problem Description

The problem requires us to write a function that takes two non-negative integer numbers as strings, num1 and num2, and returns their sum, also as a string. We must achieve this without using any built-in library functions for handling large numbers, such as BigInteger, and we are not allowed to directly convert the input strings into integers. This is a common requirement when the numbers involved can exceed the typical integer limits of the programming language, which might lead to overflow issues.

Intuition

To solve this problem, we need to mimic the way we perform addition by hand. We usually start adding the digits from the rightmost side (the least significant digit) and carry over any overflow to the next digit to the left. This process is repeated until all digits are processed.

For the implementation:

  1. We initialize pointers for both input strings at their respective ends (rightmost digits).
  2. We also initialize a variable c to keep track of the carryover during addition.
  3. We iterate through both strings from right to left, digit by digit, adding corresponding digits along with any carryover from the previous step.
  4. If one string is shorter and we run out of digits, we simply treat the missing digits as 0.
  5. As we add digits, we calculate both the digit that should be in the current position (v) and the new carryover (c) for the next position to the left.
  6. We append the result of the current single-digit addition to an answer list.
  7. After processing all digits (including the final carryover if it exists), we have our answer in reverse. We reverse it and join the list into a string.
  8. That string is then returned as the result.

With this approach, we can handle the addition of numbers of any size, as long as they fit into the computer's memory as strings.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The implementation of the solution involves a few crucial steps and uses basic data structures like lists and strings. Here's a breakdown of the approach:

  1. Initialize Indices: We start by initializing two indices, i and j, to point to the last characters of num1 and num2 respectively. These indices will be used to traverse the strings from right to left.

  2. Result List: An empty list ans is created to store the digits of the result as we calculate them.

  3. Carry Variable: A variable c is initialized to 0. This variable will be responsible for holding the carry that may come from the addition of two digits that sum more than 9.

  4. Iterating Backwards: Using a while loop, we iterate over the digits of the numbers from right to left. This loop continues until both indices i and j have traversed all the digits in their respective strings and there is no carry leftover.

  5. Adding Digits: Inside the loop, we add corresponding digits from num1 and num2. If one of the strings has been fully traversed (i.e., the index is less than 0), we treat the missing digit as 0.

  6. Handling Carry and Value: We calculate both the carry and the value of the current digit we are processing using divmod. divmod(a + b + c, 10) gives us the carry for the next addition, and the digit to append to our result in this position.

  7. Appending the Result: We append the value v as a string to our ans list.

  8. Updates: We decrement both indices i and j by 1 to move to the next digits on the left.

  9. Finalizing the Result: After processing all digits and the carry, we join the reversed ans list into a string and return it.

By iterating in reverse and using a simple carry system, this algorithm efficiently mimics manual addition, avoiding any potential overflow issues associated with large integer values.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's walk through a simple example. Consider the input strings num1 = "123" and num2 = "456". We want to find their sum.

  1. Initialize Indices: Initialize i = 2 (the index of the last character '3' in num1) and j = 2 (the index of the last character '6' in num2).

  2. Result List: Create an empty list ans to store the result digits.

  3. Carry Variable: Initialize the carry variable c to 0.

  4. Iterating Backwards: Since i and j are both not less than 0, and c is 0, we enter the while loop.

  5. Adding Digits: Add the digits at i and j indices from num1 and num2. For the first iteration, these are 3 + 6 = 9. No carry here, so c remains 0.

  6. Appending the Result: Append '9' to ans, making it ['9'].

  7. Updates: Decrement i and j to 1.

  8. Iterating Backwards - Next Step: i and j are still not less than 0, we continue the loop.

  9. Adding Digits - Next Step: Now i = 1 and j = 1, so we add '2' and '5' plus the carry (0). The sum is 7. We append '7' to ans, making it ['9', '7'].

  10. Updates - Next Step: Decrement i and j to 0.

  11. Iterating Backwards - Next Step: i and j are both 0, we continue the loop.

  12. Adding Digits - Last Digit: Now i = 0 and j = 0, we add '1' and '4'. The sum is 5. We append '5' to ans, making it ['9', '7', '5'].

  13. Updates - Final Update: Decrement i and j to -1.

  14. Finalizing the Result: We exit the loop since i and j are both less than 0 and c is 0, so we reverse ans to get ['5', '7', '9'], and join it into a string to return '579'.

Thus, the string sum of num1 and num2 is '579'.

Solution Implementation

1class Solution:
2    def addStrings(self, num1: str, num2: str) -> str:
3        """Add two non-negative numbers represented as strings."""
4        index1, index2 = len(num1) - 1, len(num2) - 1  # Start from the end of both strings
5        result = []  # Result list to store the addition results
6        carry = 0  # Initialize carry to 0 for addition
7      
8        # Loop until both strings have been processed or there is a carry
9        while index1 >= 0 or index2 >= 0 or carry:
10            digit1 = 0 if index1 < 0 else int(num1[index1])  # Get current digit or 0 if index is out of range
11            digit2 = 0 if index2 < 0 else int(num2[index2])  # Same for second number
12            carry, value = divmod(digit1 + digit2 + carry, 10)  # Add digits and carry, then divide by 10 for new carry and digit
13            result.append(str(value))  # Append the computed digit to result
14            index1, index2 = index1 - 1, index2 - 1  # Move to next digits
15      
16        return "".join(reversed(result))  # Reverse the result list and convert it to a string
17      
18    def subStrings(self, num1: str, num2: str) -> str:
19        """Subtract two non-negative numbers represented as strings."""
20        len1, len2 = len(num1), len(num2)
21        negative_result = len1 < len2 or (len1 == len2 and num1 < num2)  # Determine if result should be negative
22        # Swap numbers if the result is going to be negative
23        if negative_result: 
24            num1, num2 = num2, num1
25
26        index1, index2 = len(num1) - 1, len(num2) - 1  # Start from the end of both strings
27        result = []  # Result list for storing subtraction results
28        borrow = 0  # Initialize borrow to 0 for subtraction
29      
30        while index1 >= 0:
31            temp = int(num1[index1]) - borrow - (0 if index2 < 0 else int(num2[index2]))
32            digit = (temp + 10) % 10  # Normalize digit and possibly take a borrow
33            result.append(str(digit))  # Append current digit to the result list
34            borrow = 1 if temp < 0 else 0  # Update borrow
35            index1, index2 = index1 - 1, index2 - 1  # Move to the next digits
36      
37        # Remove leading zeros from the result
38        while len(result) > 1 and result[-1] == "0":
39            result.pop()
40      
41        # Append '-' if the result is negative
42        if negative_result:
43            result.append("-")
44
45        return "".join(reversed(result))  # Reverse and join the result list to form the final answer
46
1class Solution {
2    // Method to add two numeric strings
3    public String addStrings(String num1, String num2) {
4        // Pointers to the end of each string
5        int i = num1.length() - 1;
6        int j = num2.length() - 1;
7        StringBuilder answer = new StringBuilder();
8        // Initialize carry to 0
9        int carry = 0;
10
11        // Process both strings from the end till both strings are processed or there is no carry left
12        while(i >= 0 || j >= 0 || carry > 0) {
13            // Get digit from string num1 if available, else use 0
14            int digit1 = i < 0 ? 0 : num1.charAt(i) - '0';
15            // Get digit from string num2 if available, else use 0
16            int digit2 = j < 0 ? 0 : num2.charAt(j) - '0';
17            // Calculate sum of digits and carry
18            carry += digit1 + digit2;
19            // Append the unit digit of sum to the answer
20            answer.append(carry % 10);
21            // Calculate new carry
22            carry /= 10;
23            // Move to the next digits in each string
24            --i;
25            --j;
26        }
27
28        // The answer is in reverse order, so reverse it to get the correct result
29        answer.reverse();
30        // Convert StringBuilder to String and return
31        return answer.toString();
32    }
33
34    // Method to subtract two numeric strings
35    public String subStrings(String num1, String num2) {
36        int length1 = num1.length(), length2 = num2.length();
37        // Check if the result will be negative
38        boolean isNegative = length1 < length2 || (length1 == length2 && num1.compareTo(num2) < 0);
39        // Swap numbers if the result is negative
40        if (isNegative) {
41            String temp = num1;
42            num1 = num2;
43            num2 = temp;
44        }
45        // Pointers to the end of each string
46        int i = num1.length() - 1, j = num2.length() - 1;
47        StringBuilder answer = new StringBuilder();
48        // Initialize borrow to 0
49        int borrow = 0;
50
51        // Process the larger number from the end
52        while(i >= 0) {
53            // Subtract borrow and digit from num2 if available, else use 0, from the digit from num1
54            borrow = (num1.charAt(i) - '0') - borrow - (j < 0 ? 0 : num2.charAt(j) - '0');
55            // Handle negative results and prepare the next borrow if necessary
56            answer.append((borrow + 10) % 10);
57            borrow = borrow < 0 ? 1 : 0;
58            // Move to the next digits
59            --i;
60            --j;
61        }
62
63        // Remove leading zeros from the answer
64        while(answer.length() > 1 && answer.charAt(answer.length() - 1) == '0') {
65            answer.deleteCharAt(answer.length() - 1);
66        }
67      
68        // Append the negative sign if the result is negative
69        if (isNegative) {
70            answer.append('-');
71        }
72      
73        // The answer is in reverse order, so reverse it to get the correct result
74        answer.reverse();
75      
76        // Convert StringBuilder to String and return
77        return answer.toString();
78    }
79}
80
1class Solution {
2public:
3    // Adds two non-negative numbers represented as strings.
4    string addStrings(string num1, string num2) {
5        int i = num1.size() - 1;
6        int j = num2.size() - 1;
7        string result;
8        int carry = 0; // Initialize the carry for addition to 0.
9
10        // Loop until all digits are processed or there is a carry.
11        while (i >= 0 || j >= 0 || carry > 0) {
12            // Get the value of current digits and add to carry.
13            int digit1 = i >= 0 ? num1[i] - '0' : 0;
14            int digit2 = j >= 0 ? num2[j] - '0' : 0;
15            carry += digit1 + digit2;
16
17            // Append the current digit to the result string.
18            result += to_string(carry % 10);
19            carry /= 10; // Calculate carry for the next iteration.
20
21            // Move to the next digits.
22            --i;
23            --j;
24        }
25
26        // Since we have added digits in reverse, reverse the string to get the final result.
27        reverse(result.begin(), result.end());
28
29        return result;
30    }
31
32    // Subtracts the smaller number from the larger number represented as strings.
33    string subStrings(string num1, string num2) {
34        // Determine if the result will be negative.
35        bool isNegative = num1.size() < num2.size() || (num1.size() == num2.size() && num1 < num2);
36        if (isNegative) {
37            // Ensure num1 is always greater than num2 for direct subtraction.
38            swap(num1, num2);
39        }
40
41        int i = num1.size() - 1;
42        int j = num2.size() - 1;
43        string result;
44        int borrow = 0; // Initialize the borrow for subtraction to 0.
45
46        // Loop until all digits of num1 are processed.
47        while (i >= 0) {
48            // Calculate current digits and subtract borrow.
49            int diff = (num1[i] - '0') - borrow - (j < 0 ? 0 : num2[j] - '0');
50            if (diff < 0) {
51                diff += 10; // If difference is negative, handle the borrow.
52                borrow = 1; // Set borrow for the next iteration.
53            } else {
54                borrow = 0; // No borrow if the difference is positive.
55            }
56
57            // Append the current digit to the result string.
58            result += to_string(diff % 10);
59
60            // Move to the next digits.
61            --i;
62            --j;
63        }
64
65        // Remove any leading zeros from the result string.
66        while (result.length() > 1 && result.back() == '0') {
67            result.pop_back();
68        }
69      
70        // If the result is negative, append the negative sign.
71        if (isNegative) {
72            result += '-';
73        }
74
75        // Since we have subtracted digits in reverse, reverse the string to get the final result.
76        reverse(result.begin(), result.end());
77
78        return result;
79    }
80};
81
1function addStrings(num1: string, num2: string): string {
2    const result = []; // Array to store the result of addition
3    let index1 = num1.length - 1; // Start from the end of num1
4    let index2 = num2.length - 1; // Start from the end of num2
5    let carryOver = false; // Flag for the carry over value
6
7    // Loop until both string indices go below zero or carry over is true
8    while (index1 >= 0 || index2 >= 0 || carryOver) {
9        // Get the current digit from num1 or 0 if index is out of bounds
10        const digit1 = index1 >= 0 ? Number(num1[index1--]) : 0;
11        // Get the current digit from num2 or 0 if index is out of bounds
12        const digit2 = index2 >= 0 ? Number(num2[index2--]) : 0;
13        // Calculate the sum of the two digits and the carry over, if any
14        const sum = digit1 + digit2 + (carryOver ? 1 : 0);
15        // If sum is greater or equal to 10, we have a new carry over
16        carryOver = sum >= 10;
17        // Push the last digit of the sum into the result array
18        result.push(sum % 10);
19    }
20    // Reverse the result array and join it to form the final result string
21    return result.reverse().join('');
22}
23
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The above Python code implements two functions, addStrings and subStrings, that operate on string representations of non-negative numbers.

addStrings Time Complexity

The function iterates over each digit of the longer input string (num1 or num2) at most once, and arithmetic computations of constant time complexity are carried out for the digits. No nested loops are present. Therefore, if m and n are the lengths of num1 and num2 respectively, the time complexity is O(max(m, n)).

addStrings Space Complexity

The space complexity is dominated by the space required for the ans array, which holds the result of the addition. The length of this array will be at most max(m, n) + 1. Therefore, the space complexity is O(max(m, n)).

subStrings Time Complexity

Similar to addStrings, the subStrings function iterates over the digits of the inputs in a single pass. Comparisons and subtractions of constant time complexity are carried out. Thus, if m is the length of num1 and n is the length of num2, the time complexity is again O(max(m, n)).

subStrings Space Complexity

The space complexity is determined by the ans array here as well. In the worst case, this array's length is equal to the length of the longer input string since at most one additional digit (for a possible '-1' carried over or a leading '-' for a negative result) can be added. Hence, the space complexity is O(max(m, n)).

Overall, both functions exhibit linear time and space complexities relative to the sizes of the input strings.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫