Add Binary

                                            
class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";
        int carry = 0;
        int i = a.size() - 1;
        int j = b.size() - 1;
        
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) {
                sum += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                sum += b[j] - '0';
                j--;
            }
            carry = sum / 2;
            result = to_string(sum % 2) + result;
        }
        
        return result;
    }
};

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

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

        return sb.toString();
    }
}

                                            
class Solution(object):
    def addBinary(self, a, b):
        return bin(int(a, 2) + int(b, 2))[2:]

                                            
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
const addBinary = (a, b) => {
    let i = a.length - 1;
    let j = b.length - 1;
    let carry = 0;
    let result = '';
    
    while (i >= 0 || j >= 0 || carry > 0) {
        const sum = (+a[i] || 0) + (+b[j] || 0) + carry;
        result = (sum % 2) + result;
        carry = sum > 1 ? 1 : 0;
        i--;
        j--;
    }
    
    return result;
};

                                            
function addBinary(a: string, b: string): string {
    let result = '';
    let carry = 0;
    let i = a.length - 1;
    let j = b.length - 1;

    while (i >= 0 || j >= 0 || carry > 0) {
        const sum = (+a[i] || 0) + (+b[j] || 0) + carry;
        result = (sum % 2) + result;
        carry = sum > 1 ? 1 : 0;
        i--;
        j--;
    }

    return result;
};

                                            
class Solution {
    /**
     * @param String $a
     * @param String $b
     * @return String
     */
    function addBinary($a, $b) {
        $i = strlen($a) - 1;
        $j = strlen($b) - 1;
        $carry = 0;
        $result = "";

        while ($i >= 0 || $j >= 0 || $carry > 0) {
            $sum = $carry;
            if ($i >= 0) {
                $sum += $a[$i--] == '1' ? 1 : 0;
            }
            if ($j >= 0) {
                $sum += $b[$j--] == '1' ? 1 : 0;
            }
            $result = ($sum % 2) . $result;
            $carry = (int) ($sum / 2);
        }

        return $result;
    }
}

                                            
class Solution {
    func addBinary(_ a: String, _ b: String) -> String {
        var result = ""
        var carry = 0
        var i = a.count - 1
        var j = b.count - 1
        
        while i >= 0 || j >= 0 || carry > 0 {
            let digitA = i >= 0 ? Int(String(a[a.index(a.startIndex, offsetBy: i)]))! : 0
            let digitB = j >= 0 ? Int(String(b[b.index(b.startIndex, offsetBy: j)]))! : 0
            let sum = digitA + digitB + carry
            result = String(sum % 2) + result
            carry = sum / 2
            i -= 1
            j -= 1
        }
        
        return result
    }
}

                                            
class Solution {
    fun addBinary(a: String, b: String): String {
        var result = StringBuilder()
        var carry = 0
        var i = a.length - 1
        var j = b.length - 1

        while (i >= 0 || j >= 0 || carry > 0) {
            if (i >= 0) {
                carry += a[i] - '0'
                i--
            }
            if (j >= 0) {
                carry += b[j] - '0'
                j--
            }
            result.insert(0, (carry % 2).toString())
            carry /= 2
        }

        return result.toString()
    }
}

                                            
class Solution {
  String addBinary(String a, String b) {
    int i = a.length - 1;
    int j = b.length - 1;
    int carry = 0;
    String result = '';
    
    while (i >= 0 || j >= 0 || carry > 0) {
      int sum = carry;
      if (i >= 0) sum += a.codeUnitAt(i--) - '0'.codeUnitAt(0);
      if (j >= 0) sum += b.codeUnitAt(j--) - '0'.codeUnitAt(0);
      carry = sum ~/ 2;
      result = '${sum % 2}$result';
    }
    
    return result;
  }
}

                                            
func addBinary(a string, b string) string {
    carry := 0
    result := ""
    
    i, j := len(a)-1, len(b)-1
    
    for i >= 0 || j >= 0 || carry > 0 {
        sum := carry
        
        if i >= 0 {
            sum += int(a[i] - '0')
            i--
        }
        
        if j >= 0 {
            sum += int(b[j] - '0')
            j--
        }
        
        result = string(sum%2+'0') + result
        carry = sum / 2
    }
    
    return result
}

                                            
 # @param {String} a
# @param {String} b
# @return {String}
def add_binary(a, b)
    (a.to_i(2) + b.to_i(2)).to_s(2)
end

                                            
object Solution {
    def addBinary(a: String, b: String): String = {
        var (carry, result) = (0, "")
        var (i, j) = (a.length - 1, b.length - 1)

        while (i >= 0 || j >= 0 || carry > 0) {
            val sum = carry + (if (i >= 0) a(i) - '0' else 0) + (if (j >= 0) b(j) - '0' else 0)
            result = (sum % 2).toString + result
            carry = sum / 2
            i -= 1
            j -= 1
        }

        result
    }
}

                                            
(define/contract (add-binary a b)
  (-> string? string? string?)
  (number->string (+ (string->number a 2) (string->number b 2)) 2)
)

To solve this coding challenge, we'll break down the problem and design an algorithm that efficiently adds two binary strings and returns their sum as a binary string. Below is a highly detailed explanation of the approach, followed by the pseudocode with embedded comments for clarity.

Explanation

Understanding Binary Addition :

Adding binary numbers is similar to adding decimal numbers, but they only have two digits: 0 and 1.
Each digit's addition, similar to decimal addition, may result in a carry to the next higher bit position.

Constraints and Edge Cases :

The inputs can be of different lengths, so we need to handle cases where we add digits from one string to '0' from the other.
We must handle carries appropriately to ensure accuracy in the binary sum.
The result should not have leading zeros except for the zero itself.

Approach :

We will process both strings from the least significant bit (rightmost) to the most significant bit (leftmost). This is because binary addition moves from right to left.
Use a carry to keep track of overflow from each bit addition.
We will append the result of each bit addition to a list and then reverse this list at the end to get the correct order in the result.
Finally, we'll convert the result list back to a string.

Detailed Steps in Pseudocode

Initialize variables:

index_a

to the last index of string
a

.
index_b

to the last index of string
b

.
carry

to zero.
result

as an empty list to store the result of each bit addition.

Loop until both
index_a

and
index_b

are exhausted or there is no carry:

Extract the current bits from
a

and
b

using
index_a

and
index_b

.
Convert these bits to integers (0 if the index is out of bounds).
Add the bits together along with the carry.
The new carry will be the integer division of the sum by 2.
Append the remainder of the sum modulus 2 to
result

.
Decrement
index_a

and
index_b

.

If there is still a carry left after the loop, append it to
result

.
Reverse the
result

to get the correct binary number.
Join the elements of
result

to form the final binary string and return it.

                                            
# Pseudocode with comments

# Function to add two binary strings
function addBinary(binary_str1, binary_str2)
    # Initialize indices to point to the last characters
    index_a = length(binary_str1) - 1
    index_b = length(binary_str2) - 1
    
    # Initialize carry to 0
    carry = 0
    
    # Initialize an empty list to store the result bits
    result = []

    # Loop while there is still more to process in either binary string or there is a carry
    while index_a >= 0 or index_b >= 0 or carry != 0
        # Get the current bit from binary_str1, 0 if index is out of bounds
        bit_a = integer(binary_str1[index_a]) if index_a >= 0 else 0
        
        # Get the current bit from binary_str2, 0 if index is out of bounds
        bit_b = integer(binary_str2[index_b]) if index_b >= 0 else 0
        
        # Calculate the sum of the bits plus the carry
        total_sum = bit_a + bit_b + carry
        
        # Calculate the new carry (integer division of total_sum by 2)
        carry = total_sum // 2
        
        # Append the remainder of total_sum by 2 to the result (either 0 or 1)
        result.append(total_sum % 2)
        
        # Decrement both indices
        index_a -= 1
        index_b -= 1
    
    # After the loop, if there is still a carry left, append it
    if carry != 0
        result.append(carry)
    
    # Reverse the result to form the correct binary string
    result.reverse()

    # Join the list into a string to form the final binary number
    return join(result)

# Example case
# binary_str1 = "1010"
# binary_str2 = "1011"
# addBinary(binary_str1, binary_str2) should return "10101"

In the above pseudocode, we traverse both binary strings from the end towards the beginning, summing corresponding bits and properly accounting for any carry generated in the process. This careful approach ensures that the binary sum is correctly computed and formatted. The use of a list to store the intermediate sums adds efficiency by allowing easy appending and reversing to construct the final result string.