Add Binary | Problems

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"

Sample Input

—

Sample Output

—

Constraints

1 <= a.length, b.length <= 10^4
a and b consist only of 0 or 1
No leading zeros except 0 itself

Test Cases

Case 1

Args: ["11","1"] Expected: "100"

Case 2

Args: ["1010","1011"] Expected: "10101"

Case 3

Args: ["0","0"] Expected: "0"

Topics

Matrix BFS DFS

Bit-by-Bit Addition

Traverse both strings from right to left, adding corresponding digits along with any carry.

function addBinary(a, b) {
  let i = a.length - 1, j = b.length - 1, carry = 0, result = '';
  while (i >= 0 || j >= 0 || carry) {
    let sum = carry;
    if (i >= 0) sum += parseInt(a[i--]);
    if (j >= 0) sum += parseInt(b[j--]);
    result = (sum % 2) + result;
    carry = Math.floor(sum / 2);
  }
  return result;
}

Time: O(max(m, n)) | Space: O(max(m, n))

Saved in this browser only. Private to you.