67.md

67. Add Binary

Description

Given two binary strings, return their sum (also a binary string).

For example, a = "11" b = "1" Return "100".

Thinking process

1. Scan from the back of the two strings, add them to get the sum of the bits, update the carry accordingly

Trick

• Reverse the stringbuilder to get better performance by avoiding insert at 0 every time
• Use sb.append(sum % 2) to calculate the bit value, and carry = sum / 2 to update the carry value

public String addBinary(String a, String b) {
	int l1 = a.length() - 1;
    int l2 = b.length() - 1;
    int carry = 0;
    StringBuilder sb = new StringBuilder();
    
    while(l1 >= 0 || l2 >= 0 || carry == 1){
        int num1 = Character.getNumericValue((l1 >= 0) ? a.charAt(l1--) : '0');
        int num2 = Character.getNumericValue((l2 >= 0) ? b.charAt(l2--) : '0');
        int sum = num1 + num2 + carry;
        //update result and carry
        sb.append(sum % 2);
        carry = sum / 2;
    }
    return sb.reverse().toString();
}

Complexity

1. Two strings need to be traversed exactly once, the time complexity is hence O(n)
2. Space complexity is O(n) for storing result