Add Binary

09 August 2024 — approx 3 min read.

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

Problem Statement

LeetCode-67: Given two binary strings a and b, return their sum as a binary string.

Approach

Just like adding two decimal numbers, we can add two binary numbers by adding the digits from the rightmost digit to the leftmost digit. This way we can keep track of the carry and add it to the next digits.

In every iteration, we can add the digits from the rightmost index of both strings and the carry from the previous iteration. We can then calculate the carry for the next iteration.

We can keep adding the digits until we reach the beginning of the strings. We can then reverse the result to get the final answer.

Implementation

Here is the java implementation for the approach.

public String addBinary(String a, String b) {
    StringBuilder result = new StringBuilder();
    int carry = 0;
    int one = a.length()-1;
    int two = b.length()-1;
    while(one >= 0 && two >= 0){
        int ans = Character.getNumericValue(a.charAt(one)) +
                  Character.getNumericValue(b.charAt(two)) +
                  carry;
        result.append(ans%2);
        carry = ans/2;                        
        one--;
        two--;
    }
    while(one >= 0){
        int ans = Character.getNumericValue(a.charAt(one)) +
                  carry;
        result.append(ans%2);
        carry = ans/2;    
        one--;                    
    }
    while(two >= 0){
        int ans = Character.getNumericValue(b.charAt(two)) +
                  carry;
        result.append(ans%2);
        carry = ans/2;    
        two--;                    
    }
    if(carry > 0){
        result.append('1');
    }
    return result.reverse().toString();

}

Another approach is to use the count of the digits to evaluate the sum and carry. While adding the binary digits, the calculated sum can be one of the following values: 0, 1, 2, or 3 for the given digits x, y, and carry:

0: x=0, y=0, carry=0
1: x=1, y=0, carry=0 or x=0, y=1, carry=0
2: x=1, y=1, carry=0 or x=1, y=0, carry=1 or x=0, y=1, carry=1
3: x=1, y=1, carry=1

We can use the above information to calculate the sum and carry for the next iteration:

if calculated sum is 0 or 1, append sum to the result and set carry to 0.
if calculated sum is 2 append 0 to the result and set carry to 1.
if calculated sum is 3 append 1 to the result and set carry to 1.
if there is a carry left after the loop, append 1 to the result.
reverse the result and return the final answer.

Here is a java implementation for the approach:

public String addBinary(String a, String b) {
    StringBuilder result = new StringBuilder();
    int carry = 0;
    int one = a.length()-1;
    int two = b.length()-1;

    while (one >= 0 || two >= 0){
        int sum = 0;
        if(one >= 0 && a.charAt(one) == '1'){
            sum++;
        }
        if(two >= 0 && b.charAt(two) == '1'){
            sum++;
        }
        sum+=carry;
        if(sum == 0 || sum == 1){
            result.append(sum);
            carry = 0;
        }else if(sum == 2){
            result.append(0);
            carry = 1;
        }else{
            result.append(1);
            carry = 1;
        }
        one--;
        two--;
    }
    if(carry > 0){
        result.append('1');
    }
    return result.reverse().toString();
}

Complexity Analysis

The time complexity for this approach is \(O(n)\) where n is the length of the longer string among the two input strings. The space complexity is also \(O(n)\) as we are using a StringBuilder to store the result.

@dsadaily

Add Binary

Problem Statement

Approach

Implementation

Complexity Analysis

See Also