Binary Prefix Divisible By 5 - Solution & Explanation
Problem Statement
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], thenx0 = 1,x1 = 2, andx2 = 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 either0or1.
Approach Overview
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 1: Iterative Binary Construction
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.
Complexity
Time Complexity: O(n) where n is the length of the input array.
Space Complexity: O(n) for the storage of the answer array.
Approach 2: Using Bitwise Operations
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.
Complexity
Time Complexity: O(n).
Space Complexity: O(n) for the storage of the results array.
Approach 3: 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 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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Binary Prefix Divisible By 5 - Leetcode 1018 - Python • NeetCodeIO • 6,426 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Prefix Divisible By 5 easy or hard?
Binary Prefix Divisible By 5 Python/Java solution
How to solve Binary Prefix Divisible By 5 in O(n)?
What is the best approach for Binary Prefix Divisible By 5?
Is Binary Prefix Divisible By 5 asked at Google/Amazon/Meta?
What data structure is used in Binary Prefix Divisible By 5?
What is the time complexity of Binary Prefix Divisible By 5?
Ready to solve this problem?
Practice Binary Prefix Divisible By 5 with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor