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.
1using System;
2using System.Text;
3
4public class AddStrings {
5 public static void Main(string[] args) {
6 Console.WriteLine(AddStrings("0", "0"));
7 }
8
9 public static string AddStrings(string num1, string num2) {
10 var result = new StringBuilder();
11 int carry = 0, i = num1.Length - 1, j = num2.Length - 1;
12
13 while (i >= 0 || j >= 0 || carry != 0) {
14 int x = (i >= 0) ? num1[i] - '0' : 0;
15 int y = (j >= 0) ? num2[j] - '0' : 0;
16
17 int sum = x + y + carry;
18 result.Append(sum % 10);
19 carry = sum / 10;
20
21 i--;
22 j--;
23 }
24
25 char[] resultArray = result.ToString().ToCharArray();
26 Array.Reverse(resultArray);
27 return new string(resultArray);
28 }
29}This C# solution involves adding digits from the string ends using a loop, similar to manual addition, including carry management. The result is built using a StringBuilder and reversed before returning to present the correct order.
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#include <string>
using namespace std;
string addStrings(string num1, string num2) {
int i = num1.size() - 1, j = num2.size() - 1;
int carry = 0;
string result = "";
while (i >= 0 || j >= 0 || carry) {
int x = i >= 0 ? num1[i--] - '0' : 0;
int y = j >= 0 ? num2[j--] - '0' : 0;
int sum = x + y + carry;
result = to_string(sum % 10) + result;
carry = sum / 10;
}
return result;
}
int main() {
cout << addStrings("456", "77") << endl;
return 0;
}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 C++ approach uses string concatenation from front, conveniently managing variable lengths and carryovers through reversing pointers from string ends. The carry is accounted for through intermediate addition, and digit concatenation provides the final sum without additional reversals, keeping operations simple and direct.