Add Binary easy

Problem Statement

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1" Output: "100"

Example 2:

Input: a = "1010", b = "1011" Output: "10101"

Steps

1. Initialization: We initialize a StringBuilder to store the resulting binary string and an integer carry to 0. We also iterate through the input strings from right to left (least significant bit to most significant bit) using pointers i and j.

2. Iteration: The loop continues as long as either pointer i or j is within the bounds of their respective strings or if the carry is 1.

3. Bitwise Addition: Inside the loop, we determine the sum of the bits at the current pointers. If either pointer is out of bounds, we treat the corresponding bit as 0. The sum is calculated as sum = carry + (i >= 0 ? a.charAt(i) - '0' : 0) + (j >= 0 ? b.charAt(j) - '0' : 0). Note the subtraction of '0' to convert the character representation of '0' or '1' to its integer equivalent.

4. Result and Carry: The current bit in the result is obtained as sum % 2. The new carry is calculated as sum / 2. The bit is appended to the StringBuilder.

5. Pointer Update: The pointers i and j are decremented to move to the next bits.

6. Final Result: After the loop, if the carry is still 1, we append a '1' to the result. Finally, we reverse the StringBuilder to get the correct order of bits and return its string representation.

Explanation

The algorithm simulates binary addition by processing the bits from right to left. Each bit addition can result in a sum of 0, 1, or 2. A sum of 0 or 1 is directly added to the result, while a sum of 2 means we add 0 to the result and carry-over 1 to the next higher bit. This process continues until all bits are processed and any remaining carry is added. The use of a StringBuilder allows for efficient concatenation of the resulting bits.

Code

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;

        while (i >= 0 || j >= 0 || carry == 1) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                sum += b.charAt(j) - '0';
                j--;
            }
            sb.append(sum % 2);
            carry = sum / 2;
        }

        return sb.reverse().toString();
    }
}

Complexity

• Time Complexity: O(max(m, n)), where m and n are the lengths of strings a and b respectively. This is because we iterate through the strings once.
• Space Complexity: O(max(m, n)) in the worst case, due to the StringBuilder which stores the result. In the best case it is O(1) if both input strings are empty.