Solution For Add Binary

Problem Statement:

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example:

Input: a = “1010”, b = “1011”
Output: “10101”

Explanation:
1010
1011

10101

Solution:

For the given problem, we can take two pointers starting from the end of the binary strings a and b, to calculate the sum bit by bit, and then carry the remainder to the next bit. If the sum is greater than 1, (1+1) would indicate that a carry (1) is required for the next bit.

Algorithm:

1. Start from the last digit of both the strings.
2. Initialize three variables to store carry, sum and result.
3. Traverse the strings from the end to the start.
4. Calculate the sum of bits at the current index, carry and the previous carry.
5. If the sum is 0 or 1, update the carry to 0 and the sum to the value of the sum.
6. If the sum is 2 or 3, update the carry to 1 and the sum to the remainder of the sum/2.
7. Append the sum to the result string.
8. If there is still a carry remaining after the loop iteration, append it to the result.
9. Reverse the resultant string and return the answer.

A code snippet in Python is given below:

def addBinary(a: str, b: str) -> str:
i, j = len(a)-1, len(b)-1
carry, res = 0, ''
while i >= 0 or j >= 0:
cur_sum = carry
if i >= 0:
cur_sum += int(a[i])
i -= 1
if j >= 0:
cur_sum += int(b[j])
j -= 1
if cur_sum < 2:
carry = 0
res += str(cur_sum)
else:
carry = 1
res += str(cur_sum % 2)
if carry:
res += str(carry)
return res[::-1]

Time Complexity: O(n), where n is the length of the longest input string.

Space Complexity: O(n), where n is the length of the resultant string.

Step by Step Implementation For Add Binary

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() -1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - '0';
            if (i >= 0) sum += a.charAt(i--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

def addBinary(a, b):
    
    # initialize result variable to store sum
    result = ""
    
    # initialize carry variable to store carry
    carry = 0
    
    # loop through both strings starting from the end
    for i in range(1, max(len(a), len(b)) + 1):
        
        # get the ith digit from both strings
        # if the string is shorter than i, assume digit is 0
        a_digit = int(a[-i]) if i <= len(a) else 0
        b_digit = int(b[-i]) if i <= len(b) else 0
        
        # sum the digits and carry
        digit_sum = a_digit + b_digit + carry
        
        # if the sum is 2 or 3, set carry to 1
        if digit_sum >= 2:
            carry = 1
            
        # if the sum is 1 or 3, add 1 to the result
        if digit_sum % 2 == 1:
            result = "1" + result
            
        # if the sum is 0 or 2, add 0 to the result
        else:
            result = "0" + result
            
    # if carry is 1 after finishing the loop, add 1 to the result
    if carry == 1:
        result = "1" + result
        
    return result

var addBinary = function(a, b) {
    // your code goes here
};

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

public class Solution {
    public string AddBinary(string a, string b) {
        // initialize result string to empty
        string result = "";
        
        // initialize carry to 0
        int carry = 0;
        
        // initialize index to the end of both strings
        int i = a.Length - 1;
        int j = b.Length - 1;
        
        // while we haven't reached the beginning of either string
        while (i >= 0 || j >= 0) {
            // initialize sum to carry
            int sum = carry;
            
            // if we haven't reached the beginning of string a, add the current character to sum
            if (i >= 0) {
                sum += a[i] - '0';
            }
            
            // if we haven't reached the beginning of string b, add the current character to sum
            if (j >= 0) {
                sum += b[j] - '0';
            }
            
            // if sum is 0 or 1, add sum to result and set carry to 0
            // otherwise, add 1 to result and set carry to 1
            result = (sum % 2).ToString() + result;
            carry = sum / 2;
            
            // move to the next character in both strings
            i--;
            j--;
        }
        
        // if carry is 1, add it to the front of the result string
        if (carry == 1) {
            result = "1" + result;
        }
        
        // return the result string
        return result;
    }
}