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 <= 104num1 and num2 consist of only digits.num1 and num2 don't have any leading zeros except for the zero itself.The key idea in Add Strings is to simulate how addition is performed manually. Since the numbers are provided as strings, they cannot be directly converted to large integers in some environments. Instead, traverse both strings from right to left, adding digits one by one just like traditional column addition.
Use two pointers starting at the end of each string and maintain a carry value. Convert each character digit using char - '0', compute the sum of the digits and the carry, and append the resulting digit to the output. Continue processing until both strings are fully traversed and no carry remains.
Because each digit is processed once, the approach runs in O(n) time where n is the length of the longer string. The extra space mainly comes from building the result string, which is also O(n). This technique is a classic string simulation problem frequently asked in interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Digit-by-digit simulation using two pointers | O(n) | O(n) |
Ashish Pratap Singh
This approach involves reversing both input strings, then iterating through them to sum up each digit, similar to manual addition from the rightmost digit. This technique simplifies handling the carry over during addition.
Time Complexity: O(n), where n is the maximum length of num1 or num2.
Space Complexity: O(n), for the result array.
1def addStrings(num1: str, num2: str) -> str:
2 result = []
3 carry = 0
4 i, j = len(num1) - 1, len(num2) - 1
5
6 while i >= 0 or j >= 0 or carry:
7 x = int(num1[i]) if i >= 0 else 0
8 y = int(num2[j]) if j >= 0 else 0
9
10 sum_ = x + y + carry
11 result.append(str(sum_ % 10))
12 carry = sum_ // 10
13
14 i -= 1
15 j -= 1
16
17 return ''.join(reversed(result))
18
19# Example usage:
20print(addStrings("11", "123"))This Python implementation efficiently processes input strings num1 and num2 using a loop to sum digits from back to front, handling carries. The final sum is built using a list for ease of reversal and joined into a single string result.
This approach deploys two pointers, initially positioned at the end of each input string. We process each character one by one, moving the pointers from the rightmost end towards the start of each string. This allows us to readily manage the carry as we compute the sum step-by-step.
Time Complexity: O(n), where n is the maximum length of num1 or num2.
Space Complexity: O(n), necessary for the dynamically allocated result string.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews because it tests understanding of string manipulation and arithmetic simulation. It also checks whether candidates can avoid direct integer conversion and handle carry logic correctly.
A simple string builder or character buffer is typically used to store the result while processing digits. Since digits are generated from least significant to most significant, many solutions append digits and reverse the final string.
The optimal approach simulates manual addition from right to left. Two pointers iterate through the strings while maintaining a carry value, and digits are added step by step. This ensures linear time complexity relative to the length of the longer string.
Some interview variations restrict using built-in big integer conversions because the numbers may be extremely large. Implementing the addition manually ensures the solution works for arbitrarily long numeric strings.
The Python function addStrings handles addition across variable-length strings via iteration in reverse order, merging carry logic with character processing. Utilization of int type conversion allows precise digit handling, supporting list-based result formation for concise finalization.