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"

Hm, this problem was marked as easy, but for me, it was a brain fucker problem. Honestly, I got kinda the same problem in MANGA (FAANG).

I will try to explain approach step by step:

0) We will talk about first example

1) We should prepare arrays of characters like a aCh = ['1','1'] and bCh['1']

2) NOTE that char '1' - char '0' will give us int 1. Yes yes, that is a feature of working with symbols.

3) Based on this feature, we can calculate the sum of aInt + bInt.

4) But we have to remember about carry. Because 1 + 1 gives us 0 and carry 1 for the next pair of characters.

5) Based on carry our sum will be carry + aInt + bInt.

6) Ok, but how we will iterate over arrays? We should prepare 2 reader pointers. It can be aReader and bReader. All this pointers will start from array.length - 1.

Important. That was my mistake on Google onsite interview. I have started from zero index. But I have to start from the end. Because we use carry and should start from the first digit.

7) We will iterate while aReader and bReader >= 0

8) What next? Next we should fill rest of the digits. Becayse for example we can have 2 strings as 10101010 and 11. And we should fill the rest of the first string.

That is why we should add 2 additional while cycles.

9) And what is next? We should additionally check carry and add it to the result if carry is bigger than 0.

Please write me if you have any questions. https://t.me/crack_code_interview

public String addBinary(String a, String b) {
    char[] aCh = a.toCharArray();
    char[] bCh = b.toCharArray();
     
    int aRead = aCh.length - 1;
    int bRead = bCh.length - 1;
    int carry = 0;
    StringBuilder rez = new StringBuilder();
    while(aRead >= 0 && bRead >= 0) {
      int aI = aCh[aRead] - '0';
      int bI = bCh[bRead] - '0';
       
      int sum = carry + aI + bI;
       
      int dig = sum % 2;
      carry = sum / 2;
      rez.append(dig);
      aRead--;
      bRead--;
    }
    while(aRead >= 0){
      int aI = aCh[aRead] - '0';
      int sum = carry + aI;
      int dig = sum % 2;
      carry = sum / 2;
      rez.append(dig);
      aRead--;
    }
    while(bRead >= 0){
      int bI = bCh[bRead] - '0';
      int sum = carry + bI;
      int dig = sum % 2;
      carry = sum / 2;
      rez.append(dig);
      bRead--;
    }
    if (carry == 1){
      rez.append(carry);
    }
    return rez.reverse().toString();
  }