# Leetcode Add Binary problem solution

Apr 20, 2023

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();
}
}

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.