Add Binary (LeetCode #67)

Problem Statement

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

Approach

This is a straight forward problem. We will use the same approach that we use for adding two decimal numbers.

Below are the steps -

1. Keep a variable carry.
2. Scan the strings from right to left.
3. Calculate sum by adding the two bits represented by the characters and add carry to it.
4. Take the sum modulo 2 (sum % 2) (because it's binary, duh 😃) and add it in the front of the existing result string.
5. Update the carry by taking sum / 2 for the next iteration.
6. Check if the value of the carry is more than zero after the last iteration and if exists, add it to the front of the result.

And that's it! We have just added two binary srings. We should be proud of ourselves 👏.

The code in Java, JavaScript and Python is below -

Java

public class AddBinary {
    public String addBinary(String a, String b) {
        // Resultant String
        StringBuilder result = new StringBuilder();
        // Indices for a and b
        int i = a.length() - 1;
        int j = b.length() - 1;
        // Carry
        int carry = 0;
        while (i >= 0 || j >= 0) {
            // Sum of two bits
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            // Add the bit to the result
            result.insert(0, sum % 2);
            // Modify carry
            carry = sum / 2;
        }
        // Final check if carry exists
        if (carry > 0) {
            result.insert(0, 1);
        }
        return result.toString();
    }
}

JavaScript

var addBinary = function (a, b) {
    // Resultant string
    let result = "";
    // Indices for a and b
    let i = a.length - 1;
    let j = b.length - 1;
    // Carry
    let carry = 0;
    while (i >= 0 || j >= 0) {
        // Sum of two bits
        let sum = carry;
        if (i >= 0) {
            sum += a[i--] - '0';
        }
        if (j >= 0) {
            sum += b[j--] - '0';
        }
        // Add the bit to the result
        result = sum % 2 + result;
        // Modify carry
        carry = parseInt(sum / 2);
    }
    // Final check if carry exists
    if (carry > 0) {
        result = 1 + result;
    }
    return result;
};

Python

class AddBinary:
    def addBinary(self, a: str, b: str) -> str:
        # Resultant string
        result = ""
        # Indices for a and b
        aCount = len(a) - 1
        bCount = len(b) - 1
        # Carry
        carry = 0
        # Loop for all the characters in the strings
        while aCount >= 0 or bCount >= 0:
            # Sum of two bits
            totalSum = carry
            if aCount >= 0:
                totalSum += int(a[aCount])
                aCount -= 1
            if bCount >= 0:
                totalSum += int(b[bCount])
                bCount -= 1
            # Add the bit to te result
            result = str(totalSum % 2) + result
            # Modify carry
            carry = totalSum // 2
        # Final check if carry exists
        if carry > 0:
            result = str(1) + result
        return result

Conclusion

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.

Feel free to connect with me on Twitter and LinkedIn.

Till next time… Happy coding 😄 and Namaste 🙏!

Comments

[Аделина Насирова]

4545