Coderust: Hacking the Coding Interview/

...

/

Add Two Binary Strings

Add Two Binary Strings

Given two binary numbers as strings, return their sum as a binary string.

We'll cover the following...

Statement

Given two binary numbers as strings, implement a function that performs the binary addition on the strings and returns the output in the form of a string.

Example

g array String 1 1 0 1 0 1 0 0 array2 String 2 0 1 0 0 0 1 1 array3 Binary sum 1 1 1 0 1 1 1

Sample input

str1 = "1010100"
str2 = "0100011"

Expected output

"1110111"

Try it yourself

#include <iostream>
#include <vector>
#include <string>
using namespace std;
string AddBinary(string str1, string str2) {
	// TODO: WRITE - CODE - HERE
	return "-1";
}

Solution

To solve this problem, we do digit-by-digit addition because we cannot convert the strings to integers. The algorithm for binary addition is given below:

  • First, we initialize an empty res variable.

  • Then, we initialize the carry as 0.

  • Next, we set two pointers, p1 and p2, that point to the end of string1 and string2, respectively.

  • We traverse the strings from the end using p1 and p2 and stop when both strings are done.

  • We set x1 equal to a digit from string string1 at index p1. If p1 has reached the beginning of string1, we set x1 to 0.

  • We do the same for x2, setting x2 equal to the digit from string string2 at index p2. If p2 reaches the beginning of string2, we set x2 to 0.

  • Now, we compute the current value using value = (x1 + x2 + carry) % 2. Then, we update the carry, like so: carry = (x1 + x2 + carry) / 2. ...