In the Leetcode Add Binary problem solution 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.
Solution in C Programming
int getBitCount(char **a, char **b) {
int bitCount = 0;
while(**a != '\0' && **b != '\0') {
(*a)++;
(*b)++;
bitCount++;
}
while(**a != '\0') {
(*a)++;
bitCount++;
}
while(**b != '\0') {
(*b)++;
bitCount++;
}
return bitCount;
}
void addLeftovers(char *result, char *curPtr, char *baseAddr, int *carry) {
int num1Bits = 0;
while(curPtr >= baseAddr) {
num1Bits = (*curPtr-- == '1') + (*carry == 1);
if(num1Bits == 2) *carry = 1;
else *carry = 0;
if(num1Bits == 1) *result-- = '1';
else *result-- = '0';
}
}
char* addBinary(char *a, char *b){
char *tmpA = a;
char *tmpB = b;
int bitCount = getBitCount(&tmpA, &tmpB);
if(bitCount == 0) return NULL;
tmpA--; tmpB--; // tmpA and tmpB now point at their respective LSB's
char *result = (char *)malloc(bitCount + 1);
char *tmpResult = result + bitCount;
*tmpResult-- = '\0';
int carry = 0, num1Bits = 0;
while(tmpA >= a && tmpB >= b) {
num1Bits = (*tmpA-- == '1') + (*tmpB-- == '1') + (carry == 1);
if(num1Bits >= 2) carry = 1;
else carry = 0;
if(num1Bits == 1 || num1Bits == 3) *tmpResult-- = '1';
else *tmpResult-- = '0';
}
addLeftovers(tmpResult, tmpA, a, &carry);
addLeftovers(tmpResult, tmpB, b, &carry);
if(carry == 1) {
char *tmp = result;
result = (char *)malloc(bitCount + 2);
memcpy(&result[1], tmp, bitCount + 1);
result[0] = '1';
free(tmp);
}
return result;
}Solution in C++ Programming
class Solution {
public:
string addBinary(string a, string b) {
string res = "" ;
int i = a.length() - 1 ;
int j = b.length() - 1 ;
int carry = 0 ;
while(i >= 0 || j >= 0)
{
int sum = carry ;
if(i >= 0)
{
sum += a[i] - '0' ;
i -- ;
}
if(j >= 0)
{
sum += b[j] - '0' ;
j -- ;
}
carry = sum > 1 ? 1 : 0 ;
res += to_string(sum % 2) ;
}
if(carry)
{
res += to_string(carry) ;
}
reverse(res.begin(), res.end()) ;
return res ;
}
};Solution in Java Programming
class Solution {
public String addBinary(String a, String b) {
StringBuilder result = new StringBuilder();
int carry = 0;
int i = a.length() - 1;
int j = b.length() - 1;
while (i >= 0 || j >= 0 || carry == 1) {
int sum = carry;
if (i >= 0) {
sum += a.charAt(i) - '0';
i--;
}
if (j >= 0) {
sum += b.charAt(j) - '0';
j--;
}
result.append(sum % 2);
carry = sum / 2;
}
return result.reverse().toString();
}
}Solution in Python Programming
class Solution:
def addBinary(self, a, b):
a = str(int(a) + int(b)) #1
result = '' #2
carry = 0 #3
for i in reversed(a):
b_add = int(i) + carry #4
#5
if b_add == 2:
result += '0'
carry = 1
elif b_add > 2:
result += '1'
carry = 1
elif b_add == 0:
result += '0'
carry = 0
else:
result += '1'
carry = 0
#6
if carry > 0:
result += '1'
return result[::-1] #7
'''
#1 simply add inputs, e.g. 11 + 1 = 12 or 100110 + 1010 = 101120
#2 python strings are immutable so we create a new one to store the result
#3 store carry over digit
#4 add carry to current digit (b_add)
#5 handle cases and update carry
#6 append leftover carry to result
#7 return result in reverse order
''' Solution in C# Programming
public class Solution
{
public string AddBinary(string a, string b)
{
int i = 0;
var result = new StringBuilder();
int carry = 0;
while (i < a.Length || i < b.Length)
{
if (i < a.Length && a[a.Length - 1 - i] == '1')
carry++;
if (i < b.Length && b[b.Length - 1 - i] == '1')
carry++;
result.Insert(0, (carry % 2).ToString());
carry /= 2;
i++;
}
if (carry == 1)
{
result.Insert(0, '1');
}
return result.ToString();
}
}Also read,