#1018

Easy

LeetCode Problem Workspace

Binary Prefix Divisible By 5

Determine which binary prefixes of a given array are divisible by 5 using bit manipulation for efficient checks.

Problem Statement

You are given a binary array nums where each element is either 0 or 1. Each prefix nums[0..i] forms a binary number xi, with nums[0] as the most significant bit.

Return an array of booleans answer where answer[i] is true if the integer value of the binary prefix xi is divisible by 5, and false otherwise. Implement an efficient method without converting the entire prefix to decimal at each step.

Examples

Example 1

Input: nums = [0,1,1]

Output: [true,false,false]

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]

Example details omitted.

Constraints

1 <= nums.length <= 105
nums[i] is either 0 or 1.

Solution Approach

Iterate with Modulo Tracking

Initialize a variable current = 0. For each index i, update current as current = (current * 2 + nums[i]) % 5. Append current == 0 to the answer array. This avoids handling large numbers directly and uses bit manipulation efficiently.

Space Optimization

Instead of storing full numeric prefixes, maintain only the current modulo 5. This reduces space complexity to O(1) extra space while still producing correct boolean outputs.

Direct Boolean Array Construction

Construct the answer array on the fly during iteration without storing intermediate numbers. This ensures minimal overhead and aligns with array plus bit manipulation pattern for prefix-based calculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) as we iterate through the array once. Space complexity is O(n) for the answer array; extra space is O(1) since only the current modulo is tracked. Large arrays are handled efficiently due to modulo arithmetic and bit shift updates.

What Interviewers Usually Probe

Focus on the binary-to-decimal conversion via prefix computation.
Look for constant space optimization using modulo rather than full number storage.
Expect clarity in handling edge cases like leading zeros and small arrays.

Common Pitfalls or Variants

Common pitfalls

Attempting to convert each prefix to decimal directly, causing overflow.
Ignoring modulo arithmetic, resulting in incorrect divisibility checks.
Misinterpreting the binary order and updating prefixes incorrectly.

Follow-up variants

Check divisibility by other numbers like 3 or 7 instead of 5 using the same prefix technique.
Compute sums of binary prefixes rather than divisibility flags.
Return indices of prefixes divisible by 5 instead of boolean array.

FAQ

What is the best way to check binary prefixes for divisibility by 5?

Use a running modulo 5 computation where each prefix is updated as current = (current * 2 + nums[i]) % 5.

Can leading zeros affect the result?

No, leading zeros do not change the numeric value of the prefix; the modulo arithmetic handles them correctly.

Is converting the full binary prefix to decimal necessary?

No, direct conversion can cause overflow; using modulo updates efficiently avoids large numbers.

Does this problem use a specific algorithm pattern?

Yes, it combines Array iteration with Bit Manipulation, tracking prefixes via modulo arithmetic.

How large can nums be while staying efficient?

Arrays up to length 10^5 are handled efficiently with O(n) time and O(1) extra space using the modulo approach.

terminal

Solution

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.

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

Continue Practicing

#996 number of squareful arrays #995 minimum number of k consecutive bit flips #982 triples with bitwise and equal to zero