Description#
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.
Solutions#
Solution 1: Two Pointers#
We use two pointers $i$ and $j$ to point to the end of the two strings respectively, and start adding bit by bit from the end. Each time we take out the corresponding digits $a$ and $b$, calculate their sum $a + b + c$, where $c$ represents the carry from the last addition. Finally, we append the units digit of $a + b + c$ to the end of the answer string, and then take the tens digit of $a + b + c$ as the value of the carry $c$, and loop this process until the pointers of both strings have pointed to the beginning of the string and the value of the carry $c$ is $0$.
Finally, reverse the answer string and return it.
The time complexity is $O(\max(m, n))$, where $m$ and $n$ are the lengths of the two strings respectively. Ignoring the space consumption of the answer string, the space complexity is $O(1)$.
The following code also implements string subtraction, refer to the subStrings(num1, num2) function.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| 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])
def subStrings(self, num1: str, num2: str) -> str:
m, n = len(num1), len(num2)
neg = m < n or (m == n and num1 < num2)
if neg:
num1, num2 = num2, num1
i, j = len(num1) - 1, len(num2) - 1
ans = []
c = 0
while i >= 0:
c = int(num1[i]) - c - (0 if j < 0 else int(num2[j]))
ans.append(str((c + 10) % 10))
c = 1 if c < 0 else 0
i, j = i - 1, j - 1
while len(ans) > 1 and ans[-1] == '0':
ans.pop()
if neg:
ans.append('-')
return ''.join(ans[::-1])
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1;
StringBuilder ans = new StringBuilder();
for (int c = 0; i >= 0 || j >= 0 || c > 0; --i, --j) {
int a = i < 0 ? 0 : num1.charAt(i) - '0';
int b = j < 0 ? 0 : num2.charAt(j) - '0';
c += a + b;
ans.append(c % 10);
c /= 10;
}
return ans.reverse().toString();
}
public String subStrings(String num1, String num2) {
int m = num1.length(), n = num2.length();
boolean neg = m < n || (m == n && num1.compareTo(num2) < 0);
if (neg) {
String t = num1;
num1 = num2;
num2 = t;
}
int i = num1.length() - 1, j = num2.length() - 1;
StringBuilder ans = new StringBuilder();
for (int c = 0; i >= 0; --i, --j) {
c = (num1.charAt(i) - '0') - c - (j < 0 ? 0 : num2.charAt(j) - '0');
ans.append((c + 10) % 10);
c = c < 0 ? 1 : 0;
}
while (ans.length() > 1 && ans.charAt(ans.length() - 1) == '0') {
ans.deleteCharAt(ans.length() - 1);
}
if (neg) {
ans.append('-');
}
return ans.reverse().toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| 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;
}
string subStrings(string num1, string num2) {
int m = num1.size(), n = num2.size();
bool neg = m < n || (m == n && num1 < num2);
if (neg) {
swap(num1, num2);
}
int i = num1.size() - 1, j = num2.size() - 1;
string ans;
for (int c = 0; i >= 0; --i, --j) {
c = (num1[i] - '0') - c - (j < 0 ? 0 : num2[j] - '0');
ans += to_string((c + 10) % 10);
c = c < 0 ? 1 : 0;
}
while (ans.size() > 1 && ans.back() == '0') {
ans.pop_back();
}
if (neg) {
ans.push_back('-');
}
reverse(ans.begin(), ans.end());
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| 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)
}
func subStrings(num1 string, num2 string) string {
m, n := len(num1), len(num2)
neg := m < n || (m == n && num1 < num2)
if neg {
num1, num2 = num2, num1
}
i, j := len(num1)-1, len(num2)-1
ans := []byte{}
for c := 0; i >= 0; i, j = i-1, j-1 {
c = int(num1[i]-'0') - c
if j >= 0 {
c -= int(num2[j] - '0')
}
ans = append(ans, byte((c+10)%10+'0'))
if c < 0 {
c = 1
} else {
c = 0
}
}
for len(ans) > 1 && ans[len(ans)-1] == '0' {
ans = ans[:len(ans)-1]
}
if neg {
ans = append(ans, '-')
}
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)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| function addStrings(num1: string, num2: string): string {
let i = num1.length - 1;
let j = num2.length - 1;
const ans: number[] = [];
for (let c = 0; i >= 0 || j >= 0 || c; --i, --j) {
c += i < 0 ? 0 : +num1[i];
c += j < 0 ? 0 : +num2[j];
ans.push(c % 10);
c = Math.floor(c / 10);
}
return ans.reverse().join('');
}
function subStrings(num1: string, num2: string): string {
const m = num1.length;
const n = num2.length;
const neg = m < n || (m == n && num1 < num2);
if (neg) {
const t = num1;
num1 = num2;
num2 = t;
}
let i = num1.length - 1;
let j = num2.length - 1;
const ans: number[] = [];
for (let c = 0; i >= 0; --i, --j) {
c = +num1[i] - c;
if (j >= 0) {
c -= +num2[j];
}
ans.push((c + 10) % 10);
c = c < 0 ? 1 : 0;
}
while (ans.length > 1 && ans.at(-1) === 0) {
ans.pop();
}
return (neg ? '-' : '') + ans.reverse().join('');
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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()
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| /**
* @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 : +num1[i];
c += j < 0 ? 0 : +num2[j];
ans.push(c % 10);
c = Math.floor(c / 10);
}
return ans.reverse().join('');
};
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var subStrings = function (num1, num2) {
const m = num1.length;
const n = num2.length;
const neg = m < n || (m == n && num1 < num2);
if (neg) {
const t = num1;
num1 = num2;
num2 = t;
}
let i = num1.length - 1;
let j = num2.length - 1;
const ans = [];
for (let c = 0; i >= 0; --i, --j) {
c = +num1[i] - c;
if (j >= 0) {
c -= +num2[j];
}
ans.push((c + 10) % 10);
c = c < 0 ? 1 : 0;
}
while (ans.length > 1 && ans.at(-1) === 0) {
ans.pop();
}
return (neg ? '-' : '') + ans.reverse().join('');
};
|
