Watch 10 video solutions for Binary Prefix Divisible By 5, a easy level problem involving Array, Bit Manipulation. This walkthrough by NeetCodeIO has 6,236 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
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 <= 105nums[i] is either 0 or 1.Problem Overview: You are given a binary array where each prefix represents a binary number. For every prefix, determine whether the number formed so far is divisible by 5. The result is a boolean array where true means the prefix value is divisible by 5.
Approach 1: Iterative Binary Construction (O(n) time, O(1) space)
Treat the array as a stream of bits and build the binary number incrementally. Each new bit shifts the current value left and adds the bit: value = value * 2 + bit. Instead of storing the full number (which grows exponentially), keep only the remainder modulo 5. The update becomes remainder = (remainder * 2 + bit) % 5. If the remainder equals 0, the current prefix is divisible by 5. This approach avoids integer overflow and processes the array in a single pass.
The method works because divisibility only depends on the remainder. Keeping the remainder ensures numbers never grow large while preserving correctness. This technique is common when processing binary streams or large integers and fits naturally with array iteration problems.
Approach 2: Using Bitwise Operations (O(n) time, O(1) space)
This approach performs the same logic but uses explicit bit manipulation operations. Each new bit is appended with a left shift and OR: remainder = ((remainder << 1) | bit) % 5. The left shift multiplies the current value by 2, and the OR inserts the new bit at the least significant position.
The algorithm still tracks only the remainder modulo 5, so values remain small and constant in size. Bitwise operations make the binary construction explicit and mirror how binary numbers are actually formed in memory. This style is often preferred in low-level or performance-sensitive code where bit operations communicate intent clearly.
Recommended for interviews: The remainder-tracking approach is what interviewers expect. A naive solution that converts each prefix into a full integer leads to large numbers and unnecessary work. Showing the optimized formula (remainder * 2 + bit) % 5 demonstrates understanding of modular arithmetic and streaming computation. The bitwise version is equally optimal but mainly highlights familiarity with binary operations. Both achieve O(n) time with O(1) extra space while scanning the array once.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Binary Construction (mod tracking) | O(n) | O(1) | General solution. Clear logic using modular arithmetic while iterating through the array. |
| Bitwise Operations | O(n) | O(1) | Preferred when emphasizing binary construction or demonstrating bit manipulation knowledge. |