Formatted question description: https://leetcode.ca/all/415.html
415. Add Strings (Easy)
Given two non-negative integers num1
and num2
represented as string, return the sum of num1
and num2
.
Note:
- The length of both
num1
andnum2
is < 5100. - Both
num1
andnum2
contains only digits0-9
. - Both
num1
andnum2
does not contain any leading zero. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
Companies:
Facebook, Microsoft
Related Topics:
Math
Similar Questions:
Solution 1.
// OJ: https://leetcode.com/problems/add-strings/
// Time: O(MN)
// Space: O(1)
class Solution {
public:
string addStrings(string num1, string num2) {
string sum;
int carry = 0;
auto i1 = num1.rbegin(), i2 = num2.rbegin();
while (i1 != num1.rend() || i2 != num2.rend() || carry) {
int n = carry;
if (i1 != num1.rend()) n += *i1++ - '0';
if (i2 != num2.rend()) n += *i2++ - '0';
carry = n / 10;
sum += (n % 10) + '0';
}
reverse(sum.begin(), sum.end());
return sum;
}
};
Java
class Solution {
public String addStrings(String num1, String num2) {
if (num1.equals("0") && num2.equals("0"))
return "0";
int length1 = num1.length(), length2 = num2.length();
while (num1.length() < length2)
num1 = "0" + num1;
while (num2.length() < length1)
num2 = "0" + num2;
int totalLength = Math.max(length1, length2) + 1;
int[] sumArray = new int[totalLength];
for (int i = totalLength - 1; i > 0; i--) {
int digit1 = num1.charAt(i - 1) - '0';
int digit2 = num2.charAt(i - 1) - '0';
sumArray[i] += digit1 + digit2;
if (sumArray[i] >= 10) {
sumArray[i - 1] += sumArray[i] / 10;
sumArray[i] %= 10;
}
}
StringBuffer sb = new StringBuffer();
if (sumArray[0] != 0)
sb.append(sumArray[0]);
for (int i = 1; i < totalLength; i++)
sb.append(sumArray[i]);
String sum = sb.toString();
return sum;
}
}