DEV Community

Cover image for Add Binary (LeetCode #67)
Anirudh Sharma
Anirudh Sharma

Posted on

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();
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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 🙏!

Top comments (1)

Collapse
 
__5d05994b profile image
Аделина Насирова

4545