Binary Prefix Divisible By 5

easy array modulo bit manipulation

Problem

You are given a binary array nums (each value 0 or 1). The number x_i is the integer whose binary representation is the prefix nums[0..i] (most-significant bit first). Return a boolean array answer where answer[i] is true if and only if x_i is divisible by 5.

Inputnums = [0, 1, 1, 1, 1, 1]

Output[true, false, false, false, true, false]

Prefix values are 0, 1, 3, 7, 15, 31. Of these, 0 and 15 are divisible by 5.

nums (comma-separated 0/1)

def prefixes_div_by_5(nums):
    answer = []
    rem = 0
    for bit in nums:
        rem = (rem * 2 + bit) % 5
        answer.append(rem == 0)
    return answer

function prefixesDivBy5(nums) {
  const answer = [];
  let rem = 0;
  for (let i = 0; i < nums.length; i++) {
    rem = (rem * 2 + nums[i]) % 5;
    answer.push(rem === 0);
  }
  return answer;
}

class Solution {
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> answer = new ArrayList<>();
        int rem = 0;
        for (int i = 0; i < nums.length; i++) {
            rem = (rem * 2 + nums[i]) % 5;
            answer.add(rem == 0);
        }
        return answer;
    }
}

vector<bool> prefixesDivBy5(vector<int>& nums) {
    vector<bool> answer;
    int rem = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        rem = (rem * 2 + nums[i]) % 5;
        answer.push_back(rem == 0);
    }
    return answer;
}

Explanation

The numbers get huge fast, but we never actually need the full value — only whether it is divisible by 5. The trick is to track the remainder mod 5 as we read the bits, which always stays a tiny number between 0 and 4.

Reading one more bit means the binary number shifts left and adds that bit, i.e. value = value * 2 + bit. The same relationship holds for the remainder: rem = (rem * 2 + bit) % 5 keeps a correct running remainder at each step.

After processing each bit we record whether the prefix is divisible by 5 simply by checking rem == 0, appending that boolean to the answer list. No big-integer math is needed at all.

Example: nums = [0, 1, 1, 1, 1, 1] gives prefix values 0, 1, 3, 7, 15, 31, whose remainders mod 5 are 0, 1, 3, 2, 0, 1. So the answer is [true, false, false, false, true, false].

Time: O(n) Space: O(n)