When two binary strings are added, then the sum returned is also a binary string.
Example:
Input : x = "10", y = "01" Output: "11"
Input : x = "110", y = "011" Output: "1001" Explanation: 110 + 011 =1001
Approach 1:
Here, we need to start adding from the right side and when the sum returned is more than one then store the carry for the next digits.
Let us see a program in order to get a clear concept of the above topic.
Example:
Java
// Java program to add two binary stringsÂ
public class GFG {Â
    // Function to add two binary strings    static String add_Binary(String x, String y)    {Â
        int num1 = Integer.parseInt(x, 2);        // converting binary string into integer(decimal        // number)Â
        int num2 = Integer.parseInt(y, 2);        // converting binary string into integer(decimal        // number)Â
        int sum = num1 + num2;        // Adding those two decimal numbers and storing in        // sumÂ
        String result = Integer.toBinaryString(sum);        // Converting that resultant decimal into binary        // stringÂ
        return result;    }Â
    // Main driver method    public static void main(String args[])    {        String x = "011011", y = "1010111";Â
        System.out.print(add_Binary(x, y));    }} |
Output
1110010
Approach 2: Two Pointer
- Initialize two pointers at the end of both strings, let’s call them i and j.
- Initialize a variable carry to 0.
- While i and j are greater than or equal to 0, do the following:
- Convert the current digits at i and j to integers (0 if the pointer is out of bounds).
- Add the integers together with the carry value.
- If the sum is 0 or 1, add it to the result string and set carry to 0.
- If the sum is 2, add 0 to the result string and set carry to 1.
- If the sum is 3, add 1 to the result string and set carry to 1.
- Decrement i and j by 1.
- If there is still a carry left over, add it to the front of the result string.
- Reverse the result string and return it.
Java
import java.io.*;Â
// Classclass GFG {Â
    // Method    public static String addBinary(String x, String y)    {        int i = x.length() - 1, j = y.length() - 1;        int carry = 0;        StringBuilder result = new StringBuilder();        while (i >= 0 || j >= 0) {            int sum = carry;            if (i >= 0) {                sum += x.charAt(i) - '0';            }            if (j >= 0) {                sum += y.charAt(j) - '0';            }            if (sum == 0 || sum == 1) {                result.append(sum);                carry = 0;            }            else if (sum == 2) {                result.append("0");                carry = 1;            }            else {                result.append("1");                carry = 1;            }            i--;            j--;        }        if (carry == 1) {            result.append("1");        }        return result.reverse().toString();    }Â
    // Main driver method    public static void main(String[] args)    {        String x = "011011";        String y = "1010111";               System.out.println(addBinary(x, y));    }} |
Output
1110010
Time complexity: O(max(N, M))
Auxiliary space: O(max(N, M))
