Mastering LeetCode 67: Binary Addition Made Simple with Java

LeetCode 67 — Add Binary (Solution Link)

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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= a.length, b.length <= 104
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Algorithm

1. Input and Initialization

• Two binary strings (aa and bb) are passed as input to the addBinary method.
• The StringBuilder class is used to manipulate the binary strings efficiently (a and b).

2. Make Binary Strings Equal in Length

• Compare the lengths of the two strings:
• If one is shorter, prepend zeros to the shorter string so that both strings are of equal length.
• Use a loop to generate the required number of zeros and insert them at the beginning of the shorter string.

3. Binary Addition with Carry

• Iterate over the characters of the strings from rightmost to leftmost (simulating addition starting from the least significant bit).
• For each position i, calculate the sum of the corresponding bits from both strings and the carry from the previous step using the helper method sumBinary:
• The sumBinary method takes three characters (a[i], b[i], and carry) and returns a two-character string:
• First character represents the sum of the current position.
• Second character represents the carry for the next position.
• Update the carry and prepend the calculated sum bit to the result (sum).

4. Handle Remaining Carry

• After the loop ends, check if there is a carry left. If so, prepend it to the result.

5. Return the Result

• Convert the StringBuilder containing the binary sum (sum) to a string and return it.

6. Helper Method (sumBinary)

• Simulates binary addition for three inputs: two binary bits (a and b) and a carry bit (c).
• Uses conditional checks to determine the sum bit and carry bit for every possible combination of a, b, and c.

Complexity Analysis

1. Time Complexity:

• Equalizing Lengths: O(n), where n=max⁡(length of aa,length of bb).
• Binary Addition: O(n) for iterating through the strings.
• Total: O(n).

2. Space Complexity:

• Extra Space: O(n) for the result and padded strings.
• Total: O(n).

Java Code

public class Solution
{
    public String addBinary(String aa, String bb)
    {
        StringBuilder a = new StringBuilder(aa);
        StringBuilder b = new StringBuilder(bb);
        int diff = 0;
        StringBuilder sum = new StringBuilder();
        StringBuilder extra = new StringBuilder();
        if (a.length() > b.length())
        {
            diff = a.length() - b.length();
            extra = new StringBuilder();
            for (int i = 0; i < diff; i++)
            {
                extra.append("0");
            }
            b.insert(0, extra);
        }
        else if (a.length() < b.length())
        {
            diff = b.length() - a.length();
            extra = new StringBuilder();
            for (int i = 0; i < diff; i++)
            {
                extra.append("0");
            }
            a.insert(0, extra);
        }

        if (a.length() == b.length())
        {
            char carry = '0';
            for (int i = a.length() - 1; i >= 0; i--)
            {
                String sumString = sumBinary(a.charAt(i), b.charAt(i), carry);
                carry = sumString.charAt(1);
                sum.insert(0, sumString.charAt(0));
            }
            if (carry == '1')
            {
                sum.insert(0, carry);
            }
        }
        return sum.toString();
    }

    public static String sumBinary(char a, char b, char c)
    {
        if (a == '0' && b == '0' && c == '0')
            return "00";
        if (a == '0' && b == '0' && c == '1')
            return "10";
        if (a == '0' && b == '1' && c == '0')
            return "10";
        if (a == '0' && b == '1' && c == '1')
            return "01";
        if (a == '1' && b == '0' && c == '0')
            return "10";
        if (a == '1' && b == '0' && c == '1')
            return "01";
        if (a == '1' && b == '1' && c == '0')
            return "01";
        if (a == '1' && b == '1' && c == '1')
            return "11";
        return "00";
    }
}

Conculsion

This program efficiently handles binary addition of two strings, even if they have different lengths. The solution is clean and demonstrates how to manage carry operations in binary addition effectively.

If you found this post helpful, give it a clap 👏 and share it with your network! Have questions or feedback? Let me know in the comments. 😊