Problem

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 booleansanswer whereanswer[i]istrue ifxi is divisible by5.

Examples

Example 1

1
2
3
4

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

1
2

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

Constraints

  • 1 <= nums.length <= 10^5
  • nums[i] is either 0 or 1.

Solution

Method 1 – Prefix Modulo Tracking

Intuition

We can keep track of the current prefix as a number, but only care about its remainder modulo 5. This is because divisibility by 5 only depends on the remainder, and the number can get very large.

Approach

  1. Initialize cur = 0 and an empty answer list.
  2. For each bit in nums, update cur = (cur * 2 + bit) % 5.
  3. If cur == 0, append true to answer, else append false.
  4. Return the answer list.

Code

 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 cur = 0;
        for (int b : nums) {
            cur = ((cur << 1) + b) % 5;
            ans.push_back(cur == 0);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func prefixesDivBy5(nums []int) []bool {
    ans := make([]bool, len(nums))
    cur := 0
    for i, b := range nums {
        cur = (cur*2 + b) % 5
        ans[i] = cur == 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 cur = 0;
        for (int b : nums) {
            cur = (cur * 2 + b) % 5;
            ans.add(cur == 0);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun prefixesDivBy5(nums: IntArray): List<Boolean> {
        val ans = mutableListOf<Boolean>()
        var cur = 0
        for (b in nums) {
            cur = (cur * 2 + b) % 5
            ans.add(cur == 0)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

from typing import List
class Solution:
    def prefixesDivBy5(self, nums: list[int]) -> list[bool]:
        ans: list[bool] = []
        cur = 0
        for b in nums:
            cur = (cur * 2 + b) % 5
            ans.append(cur == 0)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn prefixes_div_by5(nums: Vec<i32>) -> Vec<bool> {
        let mut ans = Vec::with_capacity(nums.len());
        let mut cur = 0;
        for b in nums {
            cur = (cur * 2 + b) % 5;
            ans.push(cur == 0);
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)