Add Binary Strings

JavaView on GFG

Time: O(max(n,m))

Space: O(max(n,m))

Intuition

Add two binary strings. Simulate binary addition with carry, right to left.

Algorithm

1Traverse both strings from right. Add digits + carry. Append result%2, carry = result/2.
2If lengths differ, continue with remaining digits. Append final carry if non-zero.

Common Pitfalls

•Use character arithmetic: digit = char - 48. Reverse result at end.

Add Binary Strings.java

Java

// Approach: Simulate binary addition from right to left using two pointers and a carry variable.
// Time: O(max(n,m)) Space: O(max(n,m))
class Solution {
    public String addBinary(String s1, String s2) {
        StringBuilder result = new StringBuilder();

        int i = s1.length() - 1;
        int j = s2.length() - 1;

        int carry = 0;

        while (i >= 0 || j >= 0 || carry == 1) {
            int a = (i >= 0) ? s1.charAt(i--) - '0' : 0;
            int b = (j >= 0) ? s2.charAt(j--) - '0' : 0;

            int sum = a + b + carry;
            result.append((sum % 2 == 0) ? '0' : '1');
            carry = sum / 2;
        }

        result.reverse();

        i = 0;
        while (result.charAt(i) == '0') {
            i++;
        }

        return result.toString().substring(i);
    }
}

Was this solution helpful?