algoadvance

Leetcode 67. Add Binary

Problem Statement

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

You may assume that the input strings are non-empty and only contain characters 1 and 0.

Clarifying Questions

1. Q: Are the input strings guaranteed to only have ‘0’s and ‘1’s?
   • A: Yes, the input strings are guaranteed to contain only binary digits.
2. Q: Is there a maximum length for the input strings?
   • A: The problem does not specify a maximum length, so we’ll assume they can be reasonably large.
3. Q: Should the output string be the minimal representation of the binary number?
   • A: Yes, the output should not have any leading zeros, except for the binary number 0.

Strategy

1. Initialize an empty StringBuilder to store the result.
2. Initialize carry to 0 to handle any carry-over in the addition process.
3. Traverse both strings from right to left, adding corresponding bits and the carry.
4. Append the result of each addition to the StringBuilder.
5. After completing the traversal, if there is a remaining carry, append it to the StringBuilder.
6. Since the bits are added from right to left, reverse the StringBuilder to get the final binary sum string.

Code

Here’s the Java implementation of the above strategy:

public class AddBinary {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1; // Pointer for string a
        int j = b.length() - 1; // Pointer for string b
        
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i) - '0'; // Convert character to integer
                i--;
            }
            if (j >= 0) {
                sum += b.charAt(j) - '0'; // Convert character to integer
                j--;
            }
            result.append(sum % 2); // Append the binary digit
            carry = sum / 2; // Calculate the new carry
        }
        
        if (carry != 0) {
            result.append(carry); // If there is any carry left, append it
        }
        
        return result.reverse().toString(); // Reverse the result to get the correct binary sum
    }
}

Time Complexity

• Time Complexity: O(max(N, M)), where N and M are the lengths of the input strings a and b, respectively. This is because we traverse both strings once.
• Space Complexity: O(max(N, M)), which is the space required to store the resulting binary string.

This solution efficiently handles the addition of two binary strings and ensures correctness with the appropriate handling of carry-over.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?