DDSA Solutions

Add Binary Strings

JavaView on GFG
Time: O(max(n,m))
Space: O(max(n,m))

Problem Overview

Add two binary strings.

See our study guide for structured GFG and LeetCode practice.

Intuition

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

Algorithm

  1. 1Traverse both strings from right. Add digits + carry. Append result%2, carry = result/2.
  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?