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.
This approach involves constructing the number iteratively while evaluating the divisibility by 5. By maintaining the current number modulo 5, we can check divisibility efficiently without overflowing the integer limits.
The solution iteratively constructs the binary number by shifting the current number left by one (multiplying by 2) and adding the new bit. It keeps track of the number modulo 5 to ensure we deal only with small numbers, thereby checking for divisibility by 5 efficiently.
Time Complexity: O(n) where n is the length of the input array.
Space Complexity: O(n) for the storage of the answer array.
This alternative approach attempts to leverage bitwise operations to handle binary numbers more explicitly. While this is an interesting take, keep in mind the modulo method employed earlier is quite optimized already.
In this C solution, we use bitwise left shift to double the current number before adding the new bit, effectively building the binary number. The modulo operation is consistent to manage potential overflow.
Time Complexity: O(n).
Space Complexity: O(n) for the storage of the results array.
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 true to the answer array; otherwise, we add 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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Binary Construction | Time Complexity: O(n) where n is the length of the input array. |
| Using Bitwise Operations | Time Complexity: O(n). |
| Simulation | — |
| 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. |
Binary Prefix Divisible By 5 - Leetcode 1018 - Python • NeetCodeIO • 6,236 views views
Watch 9 more video solutions →Practice Binary Prefix Divisible By 5 with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor