Leetcode 67. Add Binary

Problem

Given two binary strings, we need to return their sum (also a binary string too). The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"

Output: "100"

In this example, the binary representation of 11 (in binary) is 3 and 1 (in binary) is 1. If we add 3 and 1, we get 4. In binary 4 is 100.

Example 2:

Input: a = "1010", b = "1011"

Output: "10101"

In this example, the binary representation of 1010 (in binary) is 10 and 1011 (in binary) is 11. If we add 10 and 11, we get 21. In binary 21 is 10101.

Solution

We can solve this by simulating the addition process from right to left.

Given two binary strings a and b, we go backwards from right and add the digits together. If the sum is 2 or more, we keep a carry. The sum % 2 gives us the binary digit to put in the answer string and sum / 2 gives us the carry to keep.

Once we've done this process for all digits in both strings, we reverse the answer string (since we created it by adding from right to left) and return it.

The time complexity of this solution is O(n) where n is maximum of length of string a and string b.

Java Solution

1
2java
3public class Solution {
4    public String addBinary(String a, String b) {
5        StringBuilder ans = new StringBuilder();
6        int carry = 0;
7        int i = a.length() - 1;
8        int j = b.length() - 1;
9
10        while (i >= 0 || j >= 0 || carry != 0) {
11            if (i >= 0) carry += a.charAt(i--) - '0';
12            if (j >= 0) carry += b.charAt(j--) - '0';
13            ans.append(carry % 2);
14            carry /= 2;
15        }
16        return ans.reverse().toString();
17    }
18}

Python Solution

1
2python
3class Solution:
4    def addBinary(self, a: str, b: str) -> str:
5        i, j, carry, ans = len(a) - 1, len(b) - 1, 0, []
6        while i >= 0 or j >= 0 or carry:
7            if i >= 0:
8                carry += int(a[i])
9                i -= 1
10            if j >= 0:
11                carry += int(b[j])
12                j -= 1
13            ans.append(str(carry % 2))
14            carry //= 2
15        return ''.join(ans[::-1])

C++ Solution

1
2c++
3class Solution {
4public:
5    string addBinary(string a, string b) {
6        string res = "";
7        int c = 0 , i = a.size() - 1, j = b.size() - 1;
8        while(i >= 0 || j >= 0 || c == 1)
9        {
10            c += i >= 0 ? a[i --] - '0' : 0;
11            c += j >= 0 ? b[j --] - '0' : 0;
12            res = char(c % 2 + '0') + res;
13            c /= 2;
14        }
15
16        return res;
17    }
18};

Javascript Solution

1
2javascript
3var addBinary = function(a, b) {
4    let i = a.length - 1;
5    let j = b.length - 1;
6    let carry = 0;
7    let result = '';
8    while (i >= 0 || j >= 0 || carry > 0) {
9        carry += i >= 0 ? parseInt(a[i--]) : 0;
10        carry += j >= 0 ? parseInt(b[j--]) : 0;
11        result = (carry % 2) + result;
12        carry = Math.floor(carry / 2); 
13    }
14    return result;
15};

C# Solution

1
2c#
3public class Solution {
4    public string AddBinary(string a, string b) {
5        int i = a.Length - 1, j = b.Length - 1, carry = 0;
6        StringBuilder sb = new StringBuilder();
7        while (i >= 0 || j >= 0 || carry > 0) {
8            carry += i >= 0 ? a[i--] - '0' : 0;
9            carry += j >= 0 ? b[j--] - '0' : 0;
10            sb.Insert(0, (char)(carry % 2 + '0'));
11            carry /= 2;
12        }
13        return sb.ToString();
14    }
15}

Remember: always reverse the string at the end, because we are constructing the sum from right to left!## Kotlin Solution

1
2kotlin
3class Solution {
4    fun addBinary(a: String, b: String): String {
5        var i = a.length - 1
6        var j = b.length - 1
7        var carry = 0
8        var res = StringBuilder()
9        while (i >= 0 || j >= 0 || carry > 0) {
10            if (i >= 0) carry += a[i--] - '0'
11            if (j >= 0) carry += b[j--] - '0'
12            res.append(carry % 2)
13            carry /= 2
14        }
15        return res.reverse().toString()
16    }
17}

In this Kotlin solution, we also used a StringBuilder for efficiency. We go through the two input strings in reverse and handle the sum and carry in the same way as previously described.

To convert a character to an integer, Kotlin provides a feature to transform ASCII value of a character into its corresponding integer by using the minus function. It will give the integral equivalent of the character 0 or 1.

After creating the string, we reverse it and convert the StringBuilder back to a string using the toString method.

You can also create a helper function to handle the addition and carry operation, especially beneficial if you need to add more than two binary strings.

Conclusion

Even though adding two binary strings isn't a common task, it's a useful exercise for understanding bits operations and how binary addition works. These solutions can be easily adapted for more complex bit manipulation or binary mathematics problems. Always remember to think about the time and space complexity of your solutions! If you're working on a language that supports mutable strings, keep in mind that string concatenation could turn a linear time solution into a quadratic time solution. Use a StringBuilder, List or equivalent data structure to build the result string, then convert it into a string at the end.