Add Binary numbers in C++ – LeetCode Solution [Easy]

Problem Statement
Given two binary strings a and b containing only 0s and 1s, return their sum as a binary string.

Example 1:

Input: a = "110", b = "1"
Output: "111"

Example 2:

Input: a = "1001", b = "1011"
Output: "10100"

Add Binary numbers solution

Approach

This problem could be solved in O(N) time complexity, where N is the maximum of the given two strings length. We could start traversing the two strings from the last and keep calculating the sum of each string’s character ie ‘0’ and ‘1’. If there’s a carry propagate it to the sum of the next digits in iteration.

Code Implementation

//
//  main.cpp
//  Add Binary [LeetCode]
//
//  Created by Himanshu on 04/10/21.
//

#include <iostream>
#include <string>
using namespace std;

string addBinary(string a, string b) {
    int carry = 0;
    int n1 = (int) a.size();
    int n2 = (int) b.size();
    string result = "";
    
    int temp = 0, i, j;
    string digit = "0";
    
    for(i=n1-1, j=n2-1; i>=0 && j>=0; i--, j--){
        temp = a[i] - 48 + b[j] - 48 + carry;
        if (temp == 3) {
            carry = 1;
            digit = '1';
        } else if (temp == 2){
            carry = 1;
            digit = '0';
        } else {
            carry = 0;
            digit = temp + 48;
        }
        result.insert(0, digit);
    }
    
    while(i>=0) {
        temp = a[i] - 48 + carry;
        if (temp == 3) {
            carry = 1;
            digit = '1';
        } else if (temp == 2){
            carry = 1;
            digit = '0';
        } else {
            carry = 0;
            digit = temp + 48;
        }
        result.insert(0, digit);
        i--;
    }
    
    while(j>=0) {
        temp = b[j] - 48 + carry;
        if (temp == 3) {
            carry = 1;
            digit = '1';
        } else if (temp == 2){
            carry = 1;
            digit = '0';
        } else {
            carry = 0;
            digit = temp + 48;
        }
        result.insert(0, digit);
        j--;
    }
    
    if(carry > 0) {
        result.insert(0, "1");
    }
    
    return result;
}

int main(int argc, const char * argv[]) {
    string result;
    cout<<"Add 1001 and 1011:"<<endl<<addBinary("1001", "1011")<<endl;
    cout<<"Add 111 and 1:"<<endl<<addBinary("111", "1")<<endl;
    cout<<"Add 10 and 001:"<<endl<<addBinary("10", "001")<<endl;
    return 0;
}

Output

Add 1001 and 1011:
10100
Add 111 and 1:
1000
Add 10 and 001:
011

Leave a Reply

Your email address will not be published.