Add Binary
Given two binary strings a and b, return their sum as a binary string.
Constraints:
- 1 <= a.length <= 10^4
- 1 <= b.length <= 10^4
- a and b consist only of '0's and '1's
- a and b have no leading zeros except possibly zero itself
Examples:
Input: a = "11", b = "1"
Output: "100"
Explanation: The sum of binary strings "11" and "1" is "100".
Input: a = "1010", b = "1011"
Output: "10101"
Explanation: The sum of binary strings "1010" and "1011" is "10101".
Solutions
Bit Manipulation
Time: O(max(m, n))Space: O(max(m, n))
The solution uses bit manipulation to add two binary strings. It iterates through the strings from right to left, adding corresponding bits and keeping track of the carry. The result is built by prepending the least significant bit of the sum to the result string.
public String addBinary(String a, String b) {
StringBuilder result = new StringBuilder();
int carry = 0;
int i = a.length() - 1;
int j = b.length() - 1;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += a.charAt(i--) - '0';
if (j >= 0) sum += b.charAt(j--) - '0';
carry = sum > 1 ? 1 : 0;
result.insert(0, sum % 2);
}
return result.toString();
}Follow-up:
How would you add two binary numbers represented as integers?
