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.
My Solution
We can solve this with the two pointer technique. One pointer points initially at the end of nums1. The other points at the end of nums2. At every iteration, we add the digits at those two positions together along with a carry and modulo the result by 10 to get the new digit. We divide the result by 10 to get the new carry. We iterate until we have exhausted all the characters of one of the strings. Finally we just add the rest of the digits of the other string along with the carry to the result. If at the end, our carry is 1, we append 1 to the result. Finally, the resulting StringBuilder is in reverse order, so we just need to reverse it and return it.
Time complexity is O(m+n), where m is the length of nums1 and n is the length of nums2 because we iterate once through both strings to generate the result. Space complexity is also O(m+n) because of the space required for the StringBuilder.
class Solution {
public String addStrings(String num1, String num2) {
int carry = 0;
int m = num1.length();
int n = num2.length();
int i = m-1;
int j = n-1;
StringBuilder sb = new StringBuilder();
while (i >= 0 && j >= 0) {
int digit1 = num1.charAt(i) - '0';
int digit2 = num2.charAt(j) - '0';
sb.append((digit1+digit2+carry) % 10);
carry = (digit1+digit2+carry) / 10;
i--;
j--;
}
while (i >= 0) {
int digit = num1.charAt(i) - '0';
sb.append((digit+carry) % 10);
carry = (digit + carry) / 10;
i--;
}
while (j >= 0) {
int digit = num2.charAt(j) - '0';
sb.append((digit+carry) % 10);
carry = (digit + carry) / 10;
j--;
}
if (carry > 0) {
sb.append(1);
}
return sb.reverse().toString();
}
}