🎨Now live: Try our Free AI Image Generation Feature

Description
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
.
Intuition
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.
Approach
- Initialize Variables:
- Use a
StringBuilder
to construct the result string. - Use an integercarry
to store the carry-over during addition. - Use indicesi
andj
to traverse the binary stringsa
andb
from the end to the beginning. - Traverse and Add:
- While there are bits to process in either string or there is a carry-over:
- Add the bits from
a
andb
at positionsi
andj
respectively to thecarry
. - Append the least significant bit of thecarry
to the result. - Update thecarry
to be the remaining part after extracting the least significant bit. - Handle Remaining Carry: - If there is any carry left after processing all bits, append it to the result.
- Construct the Final Result:
- The
StringBuilder
contains the result in reverse order, so reverse it before converting to a string.
Complexity
Time Complexity:
(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.
Space Complexity:
(O(\max(n, m))), which is the space used to store the result.
Code
C++
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;
}
};
Python
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])
Java
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();
}
}
JavaScript
var addBinary = function(a, b)
{
let sum = BigInt('0b'+a)+BigInt('0b'+b)
return sum.toString(2)
};