Math
String
Simulation
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 <= 104
num1
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.
Python3 Java C++ Go TypeScript Rust JavaScript Kotlin
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 ( '' );
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
fun addStrings ( num1 : String , num2 : String ): String {
val result = mutableListOf < Int > ()
val chars_1 = num1 . toCharArray ()
val chars_2 = num2 . toCharArray ()
var over = 0
var i = num1 . length
var j = num2 . length
while ( i > 0 || j > 0 || over > 0 ) {
val a = if ( i > 0 ) chars_1 [-- i ] - '0' else 0
val b = if ( j > 0 ) chars_2 [-- j ] - '0' else 0
val sum = a + b + over
over = sum / 10
result . add ( sum % 10 )
}
return result . reversed (). joinToString ( "" )
}
}