[LeetCode] Binary Prefix Divisible By 5

1.문제

You are given a binary array nums (0-indexed).

We define xi as the number whose binary representation is the subarray nums[0..i] (from most-significant-bit to least-significant-bit).

For example, if nums = [1,0,1], then x0 = 1, x1 = 2, and x2 = 5.

Return an array of booleans answer where answer[i] is true if xi is divisible by 5.

숫자 배열 nums 가 주어질 때 xi = nums[0...i] 의 요소들로 이루어진 이진수이다. 이진수들을 10진수로 바꾼 값이 5로 나누어지면 true를 answer[i] 값으로 해서 answer를 리턴하면 된다.

Example 1

Input: nums = [0,1,1]
Output: [true,false,false]
Explanation: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.
Only the first number is divisible by 5, so answer[0] is true.

Example 2

Input: nums = [1,1,1]
Output: [false,false,false]

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

2.풀이

1. 2진수는 자릿수가 하나 올라 갈 때 마다 2가 곱해진다.
2. 이전 이진수를 2를 곱해준 값에 현재 nums[i] 값을 더해주면 현재 이진수의 10진수 값
3. overflow 발생할수 있으므로 BigInt 사용하기

/**
 * @param {number[]} nums
 * @return {boolean[]}
 */
const prefixesDivBy5 = function (nums) {
  let number = 0;
  const answer = [];
  for (let i = 0; i < nums.length; i++) {
    number = BigInt(number) * BigInt(2) + BigInt(nums[i]); // 이전 숫자 값은 2를 곱해주고 현재 숫자를 더해준다
    number % BigInt(5) == 0 ? answer.push(true) : answer.push(false); // 5로 나누어지면 true , 아니라면 false
  }
  return answer;
};

3.결과