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 <= 104a 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).
PythonJavaC++GoTypeScriptRustC#
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])(code-box)
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();
}
}(code-box)
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;
}
};(code-box)
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)
}(code-box)
function addBinary(a: string, b: string): string {
let i = a.length - 1;
let j = b.length - 1;
const 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('');
}(code-box)
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()
}
}(code-box)
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);
}
}(code-box)
