Dare2Solve
Given two binary strings a
and b
, return their sum as a binary string. The input strings are non-empty and contain only characters 1
or 0
.
The problem is essentially about adding two binary numbers. Similar to how we add two decimal numbers digit by digit from right to left, we can add two binary numbers bit by bit from right to left, keeping track of the carry.
Initialize Variables:
StringBuilder
to construct the result string.carry
to store the carry-over during addition.i
and j
to traverse the binary strings a
and b
from the end to the beginning.Traverse and Add:
a
and b
at positions i
and j
respectively to the carry
.carry
to the result.carry
to be the remaining part after extracting the least significant bit.Handle Remaining Carry:
Construct the Final Result:
StringBuilder
contains the result in reverse order, so reverse it before converting to a string.(O(\max(n, m))), where n
and m
are the lengths of the binary strings a
and b
, respectively. This is because we traverse both strings once.
(O(\max(n, m))), which is the space used to store the result.
class Solution {
public:
string addBinary(string a, string b) {
string result = "";
int carry = 0;
int i = a.size() - 1, j = b.size() - 1;
while (i >= 0 || j >= 0 || carry == 1) {
carry += (i >= 0) ? a[i--] - '0' : 0;
carry += (j >= 0) ? b[j--] - '0' : 0;
result = char(carry % 2 + '0') + result;
carry /= 2;
}
return result;
}
};
class Solution:
def addBinary(self, a: str, b: str) -> str:
result = []
carry = 0
i, j = len(a) - 1, len(b) - 1
while i >= 0 or j >= 0 or carry:
if i >= 0:
carry += int(a[i])
i -= 1
if j >= 0:
carry += int(b[j])
j -= 1
result.append(str(carry % 2))
carry //= 2
return ''.join(result[::-1])
class Solution {
public String addBinary(String a, String b) {
StringBuilder result = new StringBuilder();
int carry = 0;
int i = a.length() - 1, j = b.length() - 1;
while (i >= 0 || j >= 0 || carry == 1) {
carry += (i >= 0) ? a.charAt(i--) - '0' : 0;
carry += (j >= 0) ? b.charAt(j--) - '0' : 0;
result.append(carry % 2);
carry /= 2;
}
return result.reverse().toString();
}
}
var addBinary = function(a, b)
{
let sum = BigInt('0b'+a)+BigInt('0b'+b)
return sum.toString(2)
};