[Leetcode]67. Add Binary

Posted on | Edited on | In | Comments: 0

67. Add Binary

題目連結
難易度：Easy

Given two binary strings a and b, return their sum as a binary string.

Example 1:

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

Example 2:

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

Example 3:

1
2
Input: digits = [0]
Output: [1]

Constraints:

  • 1 <= a.length, b.length <= 104
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

Concept

The length of string a and b might not be the same, so find the max length of them first.

Loop the string a and b from the end, calculate the sum of current a+b+carry, and remember to convert it to the Number before adding them up.

If it exceeds the string length, then the current a or b number will be zero. The current position value in the result array can be calculated by sum % 2, and the carry can be calculated by Math.floor(sum / 2)

After the for loop, if there is a carry value, unshift it to the array

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let maxLength = Math.max(a.length,b.length);
    let result = new Array(maxLength);
    let carry = 0;
    for(let i= 0; i < maxLength; i++){
        const aValue = a.length -1 -i < 0 ? 0 : Number(a[a.length -1 -i]);
        const bValue = b.length -1 -i < 0 ? 0 : Number(b[b.length -1 -i]);
        const sum = aValue + bValue + carry;
        result.unshift(sum % 2);
        carry = Math.floor(sum / 2);
    }
    if(carry){
        result.unshift(carry);
    }
    return result.join("");
    
};