Problem
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.
Examples
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"
Solution
Method 1 - Iterate from end of string and reverse
Code
C++
class Solution {
public:
string addStrings(string num1, string num2) {
int i = num1.size() - 1, j = num2.size() - 1;
string ans;
for (int c = 0; i >= 0 || j >= 0 || c; --i, --j) {
int a = i < 0 ? 0 : num1[i] - '0';
int b = j < 0 ? 0 : num2[j] - '0';
c += a + b;
ans += to_string(c % 10);
c /= 10;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
Go
func addStrings(num1 string, num2 string) string {
i, j := len(num1)-1, len(num2)-1
ans := []byte{}
for c := 0; i >= 0 || j >= 0 || c > 0; i, j = i-1, j-1 {
if i >= 0 {
c += int(num1[i] - '0')
}
if j >= 0 {
c += int(num2[j] - '0')
}
ans = append(ans, byte(c%10+'0'))
c /= 10
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return string(ans)
}
Java
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder result = new StringBuilder();
int i = num1.length() - 1;
int j = num2.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0) {
int d1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int d2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = (d1 + d2 + carry);
carry = sum / 10;
result.append(sum % 10);
i--;
j--;
}
if (carry == 1) {
result.append("1");
}
return result.reverse().toString();
}
}
JavaScript
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var addStrings = function (num1, num2) {
let i = num1.length - 1;
let j = num2.length - 1;
const ans = [];
for (let c = 0; i >= 0 || j >= 0 || c; --i, --j) {
c += i < 0 ? 0 : parseInt(num1.charAt(i), 10);
c += j < 0 ? 0 : parseInt(num2.charAt(j), 10);
ans.push(c % 10);
c = Math.floor(c / 10);
}
return ans.reverse().join('');
};
Python
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j = len(num1) - 1, len(num2) - 1
ans = []
c = 0
while i >= 0 or j >= 0 or c:
a = 0 if i < 0 else int(num1[i])
b = 0 if j < 0 else int(num2[j])
c, v = divmod(a + b + c, 10)
ans.append(str(v))
i, j = i - 1, j - 1
return "".join(ans[::-1])
Typescript
function addStrings(num1: string, num2: string): string {
const res = [];
let i = num1.length - 1;
let j = num2.length - 1;
let isOver = false;
while (i >= 0 || j >= 0 || isOver) {
const x = Number(num1[i--]) || 0;
const y = Number(num2[j--]) || 0;
const sum = x + y + (isOver ? 1 : 0);
isOver = sum >= 10;
res.push(sum % 10);
}
return res.reverse().join('');
}
Rust
impl Solution {
pub fn add_strings(num1: String, num2: String) -> String {
let mut res = vec![];
let s1 = num1.as_bytes();
let s2 = num2.as_bytes();
let (mut i, mut j) = (s1.len(), s2.len());
let mut is_over = false;
while i != 0 || j != 0 || is_over {
let mut sum = if is_over { 1 } else { 0 };
if i != 0 {
sum += (s1[i - 1] - b'0') as i32;
i -= 1;
}
if j != 0 {
sum += (s2[j - 1] - b'0') as i32;
j -= 1;
}
is_over = sum >= 10;
res.push((sum % 10).to_string());
}
res.into_iter().rev().collect()
}
}
…
Complexity
- Time:
O(n)
- Space:
O(n)