Problem
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