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