Question

1018. Binary Prefix Divisible By 5

中文文档

Description

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.

 

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.

Solutions

Solution 1

class Solution:
  def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
    ans = []
    x = 0
    for v in nums:
      x = (x << 1 | v) % 5
      ans.append(x == 0)
    return ans

class Solution {
  public List<Boolean> prefixesDivBy5(int[] nums) {
    List<Boolean> ans = new ArrayList<>();
    int x = 0;
    for (int v : nums) {
      x = (x << 1 | v) % 5;
      ans.add(x == 0);
    }
    return ans;
  }
}

class Solution {
public:
  vector<bool> prefixesDivBy5(vector<int>& nums) {
    vector<bool> ans;
    int x = 0;
    for (int v : nums) {
      x = (x << 1 | v) % 5;
      ans.push_back(x == 0);
    }
    return ans;
  }
};

func prefixesDivBy5(nums []int) (ans []bool) {
  x := 0
  for _, v := range nums {
    x = (x<<1 | v) % 5
    ans = append(ans, x == 0)
  }
  return
}

function prefixesDivBy5(nums: number[]): boolean[] {
  const ans: boolean[] = [];
  let x = 0;
  for (const v of nums) {
    x = ((x << 1) | v) % 5;
    ans.push(x === 0);
  }
  return ans;
}