Add Binary Leetcode Solution

Problem Statement

Given two binary strings a and b, we have to add these two strings and then return the result as a binary string. Binary string are the strings that contains only 0s and 1s.

Example

a = "11", b = "1"

"100"

a = "1010", b = "1011"

"10101"

Approach

For adding two binary strings we have to perform addition bit by bit. As we know addition is performed from right end moving towards left bits. Therefore we have to reverse the given strings first and then we can perform addition of its bits starting from index 0.
For storing bit addition sequence we can create a string variable res and append the sum of two bits and carry at end of the res string for each bit position. Finally we will return the res string for output.

Algorithm

• Reverse the given strings.
• Create an empty string and a carry variable. Initialise carry with 0.
• Now iterate over the given string in a while loop and add bit of first and second string along with carry. Now according to value of addition append the resultant bit to res string and also update the carry for next bit .
• At last we have output string but it is in reverse order because we have performed addition on reversed input string for our convenience. Therefore reverse the output string and finally return it.

Implementation

C++ Program for Add Binary Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

string addBinary(string a, string b) 
{      
    int carry=0;
    string res="";

    reverse(a.begin(),a.end()); 
    reverse(b.begin(),b.end());

    int i=0,sum;
    while(i<a.size() || i<b.size())
    {
        sum= carry;

        if(i<a.size()) sum+= a[i]-'0';
        if(i<b.size()) sum+= b[i]-'0';

        if(sum==0) carry=0, res+='0';
        else if(sum==1)  carry=0, res+='1';
        else if(sum==2)carry=1, res+='0';
        else carry=1, res+='1';


        i++;
    }


    if(carry==1)  res+='1';

    reverse(res.begin(),res.end());
    return res;
        
}
int main()
{
  string a = "1010"; 
  string b = "1011";
  cout<<addBinary(a,b)<<endl;
}

10101

Java Program for Add Binary Leetcode Solution

import java.util.*;

class Rextester{
    
    public static String addBinary(String a, String b) 
    {      
        int carry=0;

        StringBuilder s1=new StringBuilder(a);
        StringBuilder s2=new StringBuilder(b);
        StringBuilder res=new StringBuilder();

        s1.reverse(); 
        s2.reverse();

        int i=0,sum;
        while(i<a.length() || i<b.length())
        {
            sum= carry;

            if(i<a.length()) sum+= s1.charAt(i)-'0';
            if(i<b.length()) sum+= s2.charAt(i)-'0';

            if(sum==0) 
            {
                 carry=0;
                 res.append('0');
            }
            if(sum==1) 
            {
                 carry=0;
                 res.append('1');
             }
            if(sum==2)
            {
                carry=1;
                res.append('0');
            }
           if(sum==3) 
            {
                carry=1;
                res.append('1');
            }

            i++;
        }
    
        if(carry==1)   res.append('1');

        res.reverse();
        return res.toString();
        
    }
    
  public static void main(String args[])
    {
        String a = "1010"; 
        String b = "1011";
        System.out.println(addBinary(a,b));
    }
}

10101

Complexity Analysis for Add Binary Leetcode Solution

Time Complexity

O(max(N,M)) : Where N and M are lengths of input string. As we are traversing both the string linearly in a single loop, time complexity will be equal to maximum length out of the two input strings .

Space Complexity 

O(max(N,M)) : For storing the result in a string after addition we need string whose size is equal to max of length of the input strings .