Skip to content

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

We use a variable \(x\) to represent the current binary prefix, then traverse the array \(nums\). For each element \(v\), we left shift \(x\) by one bit, then add \(v\), and take the result modulo \(5\). If the result equals \(0\), it means the current binary prefix is divisible by \(5\), and we add \(\textit{true}\) to the answer array; otherwise, we add \(\textit{false}\) to the answer array.

The time complexity is \(O(n)\), and ignoring the space consumption of the answer array, the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
};

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

1
2
3
4
5
6
7
8
9
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;
}

Comments