Add Binary

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"

Solution:

This problem is a variation of other widespread problem, where you should sum digits. I got this problem in Google interview.

To solve it, we must iterate from the end. And step by step, we should sum elements.

For it, we prepare two pointers for two words. And decrease them step by step.

Where is a trick? We should not forget about the rest after the sum operation.

And sure, remember that one of the strings can be longer than the other. We should add the rest chars to our result.

TIP.

I use StringBuilder to work with strings. In Java, it is a more efficient way to use mutable operations with strings.

  public String addBinary(String aa, String bb) {
    char[] aChars = aa.toCharArray();
    char[] bChars = bb.toCharArray();
     
    int rest = 0;
    int readerA = aChars.length - 1;
    int readerB = bChars.length - 1;
     
    StringBuilder sb = new StringBuilder();
     
    while (readerA >= 0 && readerB >= 0){
      int a = aChars[readerA] - '0';
      int b = bChars[readerB] - '0';
      int sum = a + b + rest;
      rest = sum/2;
      sb.append(sum % 2);
       
      readerA--;
      readerB--;
    }
     
    while(readerA >= 0){
      int a = aChars[readerA] - '0';
      int sum = a + rest;
      rest = sum/2;
      sb.append(sum % 2);
      readerA--;
    }
    while(readerB >= 0){
      int b = bChars[readerB] - '0';
      int sum = b + rest;
      rest = sum/2;
      sb.append(sum % 2);
      readerB--;
    }
    if (rest != 0){
      sb.append(rest);
    }
    return sb.reverse().toString();
  }