You are given two binary strings a and b.
You must return their sum, also as a binary string.
Binary numbers use digits 0 and 1.
Addition rules are similar to normal addition, but with base 2.
Understanding the Problem
Example:
a = “11”
b = “1”
Output = “100”
Explanation:
11 (binary) = 3
1 (binary) = 1
3 + 1 = 4
4 in binary = 100
Another example:
a = “1010”
b = “1011”
Output = “10101”
Approach (Explained in Simple Language)
This problem is simple if you think about it like adding numbers on paper.
1. Start from the last characters of both strings
These represent the least significant bits.
2. Add digits along with any carry
Binary addition rules:
0 + 0 = 0
0 + 1 = 1
1 + 1 = 0 (carry 1)
1 + 1 + carry = 1 (carry 1)
3. Move leftwards in both strings
If one string ends earlier, treat missing digits as 0.
4. If carry remains at the end, append it
Example: adding 1 + 1 gives carry 1.
5. Reverse the final answer
Because we build the result from right to left.
This produces the correct binary sum.
Java Code
public class AddBinary {
public String addBinary(String a, String b) {
StringBuilder result = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry == 1) {
int bitA = (i >= 0) ? a.charAt(i) - '0' : 0;
int bitB = (j >= 0) ? b.charAt(j) - '0' : 0;
int sum = bitA + bitB + carry;
result.append(sum % 2);
carry = sum / 2;
i--;
j--;
}
return result.reverse().toString();
}
public static void main(String[] args) {
AddBinary solution = new AddBinary();
System.out.println(solution.addBinary("1010", "1011"));
}
}
Dry Run
Let’s dry run with:
a = “1010”
b = “1011”
Indexes start from the right.
i = 3, j = 3
carry = 0
result = “”
Step 1
a[i] = 0
b[j] = 1
sum = 0 + 1 + 0 = 1
result append = 1
carry = 0
result = “1”
Move left: i=2, j=2
Step 2
a[i] = 1
b[j] = 1
sum = 1 + 1 + 0 = 2
result append = 2 % 2 = 0
carry = 2 / 2 = 1
result = “10”
Move left: i=1, j=1
Step 3
a[i] = 0
b[j] = 0
sum = 0 + 0 + 1(carry) = 1
result append = 1
carry = 0
result = “101”
Move left: i=0, j=0
Step 4
a[i] = 1
b[j] = 1
sum = 1 + 1 + 0 = 2
result append = 0
carry = 1
result = “1010”
Move left: i=-1, j=-1
Step 5
Both i and j are out of bounds, but carry = 1
sum = 0 + 0 + 1 = 1
result append = 1
carry = 0
result = “10101”
Final Step
Reverse result:
“10101”
Final Output = “10101”
Why This Approach Works
Binary addition always moves from right to left.
You only need to track three values at each step:
bit from a
bit from b
carry
This makes the solution linear in time: O(n), where n is the length of the longer string.
There is no need to convert to integers because the numbers can be very large.