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.
1#include <iostream>
2#include <string>
3using namespace std;
4
5string addStrings(string num1, string num2) {
6 string result = "";
7 int carry = 0, i = num1.size() - 1, j = num2.size() - 1;
8
9 while (i >= 0 || j >= 0 || carry) {
10 int sum = carry;
11 if (i >= 0) sum += num1[i--] - '0';
12 if (j >= 0) sum += num2[j--] - '0';
13
14 result += (sum % 10) + '0';
15 carry = sum / 10;
16 }
17
18 reverse(result.begin(), result.end());
19 return result;
20}
21
22int main() {
23 string num1 = "11", num2 = "123";
24 cout << addStrings(num1, num2) << endl;
25 return 0;
26}This solution follows a similar logic to the C solution, iterating through the digits in reverse order from the two input strings. After computing the sum and carry for each pair of digits, we reverse the result string to complete the addition. The use of C++'s string class simplifies string operations, such as concatenation and reversing.
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.
This Java implementation consistently tracks additions and carry bits while moving through input strings from end towards beginning. An internal StringBuilder directs reverse concatenation, leveraging an efficient reversal at the end to obtain the final result representation.