Add Binary In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement:

You are given two binary strings, a and b. Each string represents a non-negative integer, where each character is either ‘0’ or ‘1’. You need to return their sum, also as a binary string.

Example:

Input:
a = "1010" 
b = "1011"

Output:
"10101"

Approach:

The problem can be solved by simulating the binary addition process, similar to how we add numbers by hand. We’ll start adding from the rightmost bit (the least significant bit) and move leftwards. We need to keep track of the carry that might result from the addition of two bits.

Steps:

1. Initialize two pointers, one for each string a and b.
2. Initialize a carry variable to 0.
3. Traverse both strings from the rightmost bit to the leftmost bit.
4. Add corresponding bits from both strings, and include the carry from the previous operation.
5. If the sum of bits exceeds 1 (i.e., 1 + 1 = 2), set the carry to 1, and store the sum as 0 for that bit.
6. If there’s any carry left after the final addition, append it to the result.
7. Return the result in binary form.

Algorithm:

1. Initialize pointers i and j for the strings a and b, respectively, starting from the end of each string.
2. Initialize a carry variable to 0.
3. Iterate while either i or j are non-negative (i.e., there are still bits to add) or the carry is not zero.
4. For each iteration:
   • Add the bit from a[i] (if i is valid), b[j] (if j is valid), and the carry.
   • Calculate the sum and update the carry.
   • Append the result of the sum modulo 2 to the result string.
5. Return the result string.

Time Complexity:

The time complexity is O(max(n, m)), where n and m are the lengths of the two binary strings a and b. We go through both strings at most once.

Space Complexity:

The space complexity is O(max(n, m)) due to the space used to store the result string.

---

Code Implementations

1. C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* addBinary(char* a, char* b) {
    int i = strlen(a) - 1, j = strlen(b) - 1, carry = 0;
    int size = (i > j ? i : j) + 2; // Maximum length needed
    char* result = (char*)malloc(sizeof(char) * (size + 1));
    int k = 0;

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

    result[k] = '\0';

    // Reverse the result string
    for (int start = 0, end = k - 1; start < end; start++, end--) {
        char temp = result[start];
        result[start] = result[end];
        result[end] = temp;
    }

    return result;
}

int main() {
    char a[] = "1010", b[] = "1011";
    char* result = addBinary(a, b);
    printf("Sum: %s\n", result);
    free(result);
    return 0;
}

2. C++

#include <iostream>
#include <string>
using namespace std;

string addBinary(string a, string b) {
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    string result = "";

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

    return result;
}

int main() {
    string a = "1010", b = "1011";
    cout << "Sum: " << addBinary(a, b) << endl;
    return 0;
}

3. Java

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

        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';

            result.append(sum % 2);
            carry = sum / 2;
        }

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        String a = "1010", b = "1011";
        System.out.println("Sum: " + sol.addBinary(a, b));
    }
}

4. Python

def addBinary(a: str, b: str) -> str:
    i, j, carry = len(a) - 1, len(b) - 1, 0
    result = []

    while i >= 0 or j >= 0 or carry:
        sum = carry
        if i >= 0:
            sum += int(a[i])
            i -= 1
        if j >= 0:
            sum += int(b[j])
            j -= 1

        result.append(str(sum % 2))
        carry = sum // 2

    return ''.join(reversed(result))

# Test
a = "1010"
b = "1011"
print("Sum:", addBinary(a, b))

5. C#

using System;
using System.Text;

class Solution {
    public string AddBinary(string a, string b) {
        int i = a.Length - 1, j = b.Length - 1, carry = 0;
        StringBuilder result = new StringBuilder();

        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';

            result.Append(sum % 2);
            carry = sum / 2;
        }

        char[] resultArr = result.ToString().ToCharArray();
        Array.Reverse(resultArr);
        return new string(resultArr);
    }

    public static void Main() {
        Solution sol = new Solution();
        string a = "1010", b = "1011";
        Console.WriteLine("Sum: " + sol.AddBinary(a, b));
    }
}

6. JavaScript

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

    while (i >= 0 || j >= 0 || carry) {
        let sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';

        result.push(sum % 2);
        carry = Math.floor(sum / 2);
    }

    return result.reverse().join('');
}

// Test
let a = "1010", b = "1011";
console.log("Sum:", addBinary(a, b));

---

Summary:

• This approach uses a simple simulation of binary addition.
• The code works by traversing both input strings from right to left, performing bit-wise addition and handling the carry.
• The final result is built in reverse order, and then reversed before returning.