Bit Manipulation
Math
String
Simulation
Description
Given two binary strings a
and b
, return their sum as a binary string .
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
1 <= a.length, b.length <= 104
a
and b
consist only of '0'
or '1'
characters.
Each string does not contain leading zeros except for the zero itself.
Solutions
Solution 1: Simulation
We use a variable $carry$ to record the current carry, and two pointers $i$ and $j$ to point to the end of $a$ and $b$ respectively, and add them bit by bit from the end to the beginning.
The time complexity is $O(\max(m, n))$, where $m$ and $n$ are the lengths of strings $a$ and $b$ respectively. The space complexity is $O(1)$.
Python3 Java C++ Go TypeScript Rust C#
class Solution :
def addBinary ( self , a : str , b : str ) -> str :
return bin ( int ( a , 2 ) + int ( b , 2 ))[ 2 :]
1
2
3
4
5
6
7
8
9
10
11
12 class Solution {
public String addBinary ( String a , String b ) {
var sb = new StringBuilder ();
int i = a . length () - 1 , j = b . length () - 1 ;
for ( int carry = 0 ; i >= 0 || j >= 0 || carry > 0 ; -- i , -- j ) {
carry += ( i >= 0 ? a . charAt ( i ) - '0' : 0 ) + ( j >= 0 ? b . charAt ( j ) - '0' : 0 );
sb . append ( carry % 2 );
carry /= 2 ;
}
return sb . reverse (). toString ();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public :
string addBinary ( string a , string b ) {
string ans ;
int i = a . size () - 1 , j = b . size () - 1 ;
for ( int carry = 0 ; i >= 0 || j >= 0 || carry ; -- i , -- j ) {
carry += ( i >= 0 ? a [ i ] - '0' : 0 ) + ( j >= 0 ? b [ j ] - '0' : 0 );
ans . push_back (( carry % 2 ) + '0' );
carry /= 2 ;
}
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 func addBinary ( a string , b string ) string {
i , j := len ( a ) - 1 , len ( b ) - 1
ans := [] byte {}
for carry := 0 ; i >= 0 || j >= 0 || carry > 0 ; i , j = i - 1 , j - 1 {
if i >= 0 {
carry += int ( a [ i ] - '0' )
}
if j >= 0 {
carry += int ( b [ j ] - '0' )
}
ans = append ( ans , byte ( carry % 2 + '0' ))
carry /= 2
}
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 )
}
function addBinary ( a : string , b : string ) : string {
return ( BigInt ( '0b' + a ) + BigInt ( '0b' + b )). toString ( 2 );
}
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_binary ( a : String , b : String ) -> String {
let mut i = ( a . len () as i32 ) - 1 ;
let mut j = ( b . len () as i32 ) - 1 ;
let mut carry = 0 ;
let mut ans = String :: new ();
let a = a . as_bytes ();
let b = b . as_bytes ();
while i >= 0 || j >= 0 || carry > 0 {
if i >= 0 {
carry += a [ i as usize ] - b'0' ;
i -= 1 ;
}
if j >= 0 {
carry += b [ j as usize ] - b'0' ;
j -= 1 ;
}
ans . push_str ( & ( carry % 2 ). to_string ());
carry /= 2 ;
}
ans . chars (). rev (). collect ()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 public class Solution {
public string AddBinary ( string a , string b ) {
int i = a . Length - 1 ;
int j = b . Length - 1 ;
var sb = new StringBuilder ();
for ( int carry = 0 ; i >= 0 || j >= 0 || carry > 0 ; -- i , -- j ) {
carry += i >= 0 ? a [ i ] - '0' : 0 ;
carry += j >= 0 ? b [ j ] - '0' : 0 ;
sb . Append ( carry % 2 );
carry /= 2 ;
}
var ans = sb . ToString (). ToCharArray ();
Array . Reverse ( ans );
return new string ( ans );
}
}
Solution 2
Python3 TypeScript
class Solution :
def addBinary ( self , a : str , b : str ) -> str :
ans = []
i , j , carry = len ( a ) - 1 , len ( b ) - 1 , 0
while i >= 0 or j >= 0 or carry :
carry += ( 0 if i < 0 else int ( a [ i ])) + ( 0 if j < 0 else int ( b [ j ]))
carry , v = divmod ( carry , 2 )
ans . append ( str ( v ))
i , j = i - 1 , j - 1
return '' . join ( ans [:: - 1 ])
1
2
3
4
5
6
7
8
9
10
11
12 function addBinary ( a : string , b : string ) : string {
let i = a . length - 1 ;
let j = b . length - 1 ;
let ans : number [] = [];
for ( let carry = 0 ; i >= 0 || j >= 0 || carry ; -- i , -- j ) {
carry += ( i >= 0 ? a [ i ] : '0' ). charCodeAt ( 0 ) - '0' . charCodeAt ( 0 );
carry += ( j >= 0 ? b [ j ] : '0' ). charCodeAt ( 0 ) - '0' . charCodeAt ( 0 );
ans . push ( carry % 2 );
carry >>= 1 ;
}
return ans . reverse (). join ( '' );
}