[Facebook] 67. Add Binary

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 1:

Input: a = "11", b = "1" Output: "100"

Example 2:

Input: a = "1010", b = "1011" Output: "10101"

 

Constraints:

• Each string consists only of '0' or '1' characters.
• 1 <= a.length, b.length <= 10^4
• Each string is either "0" or doesn't contain any leading zero.

두 개의 이진 문자열이 주어지면 그 합계를 반환합니다 (또한 이진 문자열).

입력 문자열은 모두 비어 있지 않으며 문자 1 또는 0 만 포함합니다.

예 1 :

입력 : a = "11", b = "1"출력 : "100"

예 2 :

입력 : a = "1010", b = "1011"출력 : "10101"



제약 :

각 문자열은 '0'또는 '1'문자로만 구성됩니다.
1 <= a.length, b.length <= 10 ^ 4
각 문자열은 "0"이거나 선행 0을 포함하지 않습니다.

---

 

Solution

---

Overview

There is a simple way using built-in functions:

• Convert a and b into integers.

• Compute the sum.

• Convert the sum back into binary form.

class Solution {
  public String addBinary(String a, String b) {
    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
  }
}

The overall algorithm has \mathcal{O}(N + M)O(N+M) time complexity and has two drawbacks which could be used against you during the interview.

1 . In Java this approach is limited by the length of the input strings a and b. Once the string is long enough, the result of conversion into integers will not fit into Integer, Long or BigInteger:

• 33 1-bits - and b doesn't fit into Integer.

• 65 1-bits - and b doesn't fit into Long.

• 500000001 1-bits - and b doesn't fit into BigInteger.

To fix the issue, one could use standard Bit-by-Bit Computation approach which is suitable for quite long input strings.

2 . This method has quite low performance in the case of large input numbers.

One could use Bit Manipulation approach to speed up the solution.

 

개요

내장 함수를 사용하는 간단한 방법이 있습니다.

a와 b를 정수로 변환합니다.

합계를 계산하십시오.

합계를 이진 형식으로 다시 변환합니다.

전체 알고리즘에는 \ mathcal {O} (N + M) O (N + M) 시간 복잡도가 있으며 인터뷰 중에 사용할 수있는 두 가지 단점이 있습니다.

1 . Java에서이 접근 방식은 입력 문자열 a 및 b의 길이로 제한됩니다. 문자열이 충분히 길면 정수로의 변환 결과는 Integer, Long 또는 BigInteger에 맞지 않습니다.

33 1 비트-그리고 b는 정수에 맞지 않습니다.

65 1 비트-그리고 b는 Long에 맞지 않습니다.

500000001 1 비트-그리고 b는 BigInteger에 맞지 않습니다.

이 문제를 해결하기 위해 매우 긴 입력 문자열에 적합한 표준 비트 별 계산 방식을 사용할 수 있습니다.

2. 이 방법은 입력 수가 많은 경우 성능이 매우 낮습니다.

솔루션의 속도를 높이기 위해 Bit Manipulation 접근 방식을 사용할 수 있습니다.

---

Approach 1: Bit-by-Bit Computation

Algorithm

That's a good old classical algorithm, and there is no conversion from binary string to decimal and back here. Let's consider the numbers bit by bit starting from the lowest one and compute the carry this bit will add.

Start from carry = 0. If number a has 1-bit in this lowest bit, add 1 to the carry. The same for number b: if number b has 1-bit in the lowest bit, add 1 to the carry. At this point the carry for the lowest bit could be equal to (00)_2(00)2​, (01)_2(01)2​, or (10)_2(10)2​.

Now append the lowest bit of the carry to the answer, and move the highest bit of the carry to the next order bit.

Repeat the same steps again, and again, till all bits in a and b are used up. If there is still nonzero carry to add, add it. Now reverse the answer string and the job is done.

 

접근 방식 1 : 비트 별 계산

연산

그것은 좋은 오래된 고전 알고리즘이며, 이진 문자열에서 십진수로 그리고 여기로 돌아가는 변환이 없습니다. 가장 낮은 것부터 시작하여 비트별로 숫자를 고려하고이 비트가 추가 할 캐리를 계산해 봅시다.

캐리 = 0 에서 시작합니다. 숫자 a가이 최하위 비트에 1 비트를 가지고 있으면 캐리에 1을 더합니다. b 번도 동일합니다. b 번이 최하위 비트에 1 비트가 있으면 캐리에 1을 더합니다. 이 시점에서 가장 낮은 비트에 대한 캐리는 (00) _2 (00) 2, (01) _2 (01) 2 또는 (10) _2 (10) 2와 같을 수 있습니다.

이제 캐리의 가장 낮은 비트를 답에 추가하고 캐리의 가장 높은 비트를 다음 순서 비트로 이동합니다.

a와 b의 모든 비트가 다 사용될 때까지 동일한 단계를 반복합니다. 추가 할 캐리가 여전히 0이 아닌 경우 추가합니다. 이제 응답 문자열을 뒤집 으면 작업이 완료됩니다.

 

 

1 / 7

Implementation

 

class Solution {
  public String addBinary(String a, String b) {
    int n = a.length(), m = b.length();
    if (n < m) return addBinary(b, a);
    int L = Math.max(n, m);

    StringBuilder sb = new StringBuilder();
    int carry = 0, j = m - 1;
    for(int i = L - 1; i > -1; --i) {
      if (a.charAt(i) == '1') ++carry;
      if (j > -1 && b.charAt(j--) == '1') ++carry;

      if (carry % 2 == 1) sb.append('1');
      else sb.append('0');

      carry /= 2;
    }
    if (carry == 1) sb.append('1');
    sb.reverse();

    return sb.toString();
  }
}

 

Complexity Analysis

• Time complexity: \mathcal{O}(\max(N, M))O(max(N,M)), where NN and MM are lengths of the input strings a and b.

• Space complexity: \mathcal{O}(\max(N, M))O(max(N,M)) to keep the answer.
  
  

---

Approach 2: Bit Manipulation

 

Intuition

Here the input is more adapted to push towards Approach 1, but there is popular Facebook variation of this problem when interviewer provides you two numbers and asks to sum them up without using addition operation.

No addition? OK, bit manipulation then.

How to start? There is an interview tip for bit manipulation problems: if you don't know how to start, start from computing XOR for your input data. Strangely, that helps to go out for quite a lot of problems, Single Number II, Single Number III, Maximum XOR of Two Numbers in an Array, Repeated DNA Sequences, Maximum Product of Word Lengths, etc.

Here XOR is a key as well, because it's a sum of two binaries without taking carry into account.

 

여기에서 입력은 접근 방식 1로 이동하는 데 더 적합하지만 면접관이 두 개의 숫자를 제공하고 더하기 연산을 사용하지 않고 합계를 요구할 때이 문제의 인기있는 Facebook 변형이 있습니다.

추가하지 않습니까? 좋아, 그럼 비트 조작.

시작하는 방법? 비트 조작 문제에 대한 인터뷰 팁이 있습니다. 시작하는 방법을 모르면 입력 데이터에 대한 XOR 계산부터 시작하세요. 이상하게도 단일 번호 II, 단일 번호 III, 배열에있는 두 숫자의 최대 XOR, 반복 된 DNA 시퀀스, 단어 길이의 최대 곱 등 많은 문제를 해결하는 데 도움이됩니다.

여기에서 XOR도 키입니다. 왜냐하면 그것은 고려하지 않고 두 바이너리의 합이기 때문입니다.

 

 

To find current carry is quite easy as well, it's AND of two input numbers, shifted one bit to the left.

Now the problem is reduced: one has to find the sum of answer without carry and carry. It's the same problem - to sum two numbers, and hence one could solve it in a loop with the condition statement "while carry is not equal to zero".

Algorithm

• Convert a and b into integers x and y, x will be used to keep an answer, and y for the carry.

• While carry is nonzero: y != 0:

  • Current answer without carry is XOR of x and y: answer = x^y.

  • Current carry is left-shifted AND of x and y: carry = (x & y) << 1.

  • Job is done, prepare the next loop: x = answer, y = carry.

• Return x in the binary form.

 

이제 문제가 줄어 듭니다. 캐리와 캐리없이 답의 합을 찾아야합니다. 두 개의 숫자를 더하는 것은 동일한 문제입니다. 따라서 "carry가 0이 아닐 때"라는 조건문을 사용하여 루프에서 해결할 수 있습니다.

연산

a와 b를 정수 x와 y로 변환하고 x는 답을 유지하는 데 사용되고 y는 캐리를 위해 사용됩니다.

캐리가 0이 아닌 경우 : y! = 0 :

캐리가없는 현재 대답은 x와 y의 XOR입니다 : 대답 = x ^ y.

현재 캐리는 x와 y의 왼쪽 이동 AND : 캐리 = (x & y) << 1입니다.

작업이 완료되면 다음 루프를 준비합니다. x = 답변, y = 캐리.

이진 형식으로 x를 반환합니다.

 

 

Implementation

import java.math.BigInteger;
class Solution {
  public String addBinary(String a, String b) {
    BigInteger x = new BigInteger(a, 2);
    BigInteger y = new BigInteger(b, 2);
    BigInteger zero = new BigInteger("0", 2);
    BigInteger carry, answer;
    while (y.compareTo(zero) != 0) {
      answer = x.xor(y);
      carry = x.and(y).shiftLeft(1);
      x = answer;
      y = carry;
    }
    return x.toString(2);
  }
}

 

 

This solution could be written as 4-liner in Python

 

Performance Discussion

Here we deal with input numbers which are greater than 2^{100}2100. That forces to use slow BigInteger in Java, and hence the performance gain will be present for the Python solution only. Provided here Java solution could make its best with Integers or Longs, but not with BigIntegers.

 

여기서는 2 ^ {100} 2100보다 큰 입력 숫자를 다룹니다. 따라서 Java에서 느린 BigInteger를 사용해야하므로 성능 향상은 Python 솔루션에서만 나타납니다. 여기에 제공된 Java 솔루션은 Integers 또는 Longs에서 최선을 다할 수 있지만 BigIntegers에서는 그렇지 않습니다.

 

 

Complexity Analysis

• Time complexity : \mathcal{O}(N + M)O(N+M), where NN and MM are lengths of the input strings a and b.

• Space complexity : \mathcal{O}(\max(N, M))O(max(N,M)) to keep the answer.