Binary Prefix Divisible By 5 solution and explanation
Google
9 more videos on this problem
Binary Prefix Divisible By 5 - Leetcode 1018 - PythonNeetCodeIO · 14:26 · 6K views
Binary Prefix Divisible By 5 | Important Things To Learn | Leetcode 1018 | codestorywithMIKcodestorywithMIK · 19:33 · 5K views
(Remade) Leetcode 1018 - Binary Prefix Div By 5 | ArrayNideesh Terapalli · 3:25 · 1K views
1018. Binary Prefix Divisible By 5 (Leetcode Easy)Programming Live with Larry · 3:34 · 872 views
(Old) Leetcode 1018 - Binary Prefix Div By 5 | ArrayNideesh Terapalli · 5:21 · 866 views
Daily Leetcode #2064: Nov 24, 2025 - 1018. Binary Prefix Divisible By 5Programming Live with Larry · 3:07 · 559 views
Leetcode solving 1018. Binary Prefix Divisible By 5Math Geeks · 2:31 · 257 views
1018. Binary Prefix Divisible By 5 | Leetcode Daily - PythonLeetcode Daily · 9:17 · 205 views
#LeetCode 1018 | Binary Prefix Divisible By 5 #JavaSleepy Cracker · 3:16 · 194 views
(C#)LeetCode 1018 Binary Prefix Divisible By 5zongwu yang · 2:40 · 157 views
The problem
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.
class Solution:
def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
answer = []
current_number = 0
for num in nums:
current_number = (current_number * 2 + num) % 5
answer.append(current_number == 0)
return answerimport java.util.*;
class Solution {
public List<Boolean> prefixesDivBy5(int[] nums) {
List<Boolean> answer = new ArrayList<>();
int currentNumber = 0;
for (int num : nums) {
currentNumber = (currentNumber * 2 + num) % 5;
answer.add(currentNumber == 0);
}
return answer;
}
}#include <vector>
std::vector<bool> prefixesDivBy5(std::vector<int>& nums) {
std::vector<bool> answer;
int currentNumber = 0;
for (int num : nums) {
currentNumber = (currentNumber * 2 + num) % 5;
answer.push_back(currentNumber == 0);
}
return answer;
}var prefixesDivBy5 = function(nums) {
const answer = [];
let currentNumber = 0;
nums.forEach(num => {
currentNumber = (currentNumber * 2 + num) % 5;
answer.push(currentNumber === 0);
});
return answer;
};#include <stdbool.h>
#include <stdlib.h>
bool* prefixesDivBy5(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
bool* answer = (bool*)malloc(sizeof(bool) * numsSize);
int currentNumber = 0;
for (int i = 0; i < numsSize; i++) {
currentNumber = (currentNumber * 2 + nums[i]) % 5;
answer[i] = (currentNumber == 0);
}
return answer;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<bool> PrefixesDivBy5(int[] nums) {
var answer = new List<bool>();
int currentNumber = 0;
foreach (int num in nums) {
currentNumber = (currentNumber * 2 + num) % 5;
answer.Add(currentNumber == 0);
}
return answer;
}
}Python's solution leverages list operations to store boolean values. The logic remains consistent, using a running modulo calculation to track divisibility by 5 across the input numbers.
Time Complexity: O(n).
Space Complexity: O(n) for storing results in the list.
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.
class Solution:
def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
answer = []
current_number = 0
for num in nums:
current_number = ((current_number << 1) | num) % 5
answer.append(current_number == 0)
return answerimport java.util.*;
class Solution {
public List<Boolean> prefixesDivBy5(int[] nums) {
List<Boolean> answer = new ArrayList<>();
int currentNumber = 0;
for (int num : nums) {
currentNumber = ((currentNumber << 1) | num) % 5;
answer.add(currentNumber == 0);
}
return answer;
}
}#include <vector>
std::vector<bool> prefixesDivBy5(std::vector<int>& nums) {
std::vector<bool> answer;
int currentNumber = 0;
for (int num : nums) {
currentNumber = ((currentNumber << 1) | num) % 5;
answer.push_back(currentNumber == 0);
}
return answer;
}var prefixesDivBy5 = function(nums) {
const answer = [];
let currentNumber = 0;
nums.forEach(num => {
currentNumber = ((currentNumber << 1) | num) % 5;
answer.push(currentNumber === 0);
});
return answer;
};#include <stdbool.h>
#include <stdlib.h>
bool* prefixesDivBy5(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
bool* answer = (bool*)malloc(sizeof(bool) * numsSize);
int currentNumber = 0;
for (int i = 0; i < numsSize; i++) {
currentNumber = ((currentNumber << 1) | nums[i]) % 5;
answer[i] = (currentNumber == 0);
}
return answer;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<bool> PrefixesDivBy5(int[] nums) {
var answer = new List<bool>();
int currentNumber = 0;
foreach (int num in nums) {
currentNumber = ((currentNumber << 1) | num) % 5;
answer.Add(currentNumber == 0);
}
return answer;
}
}Python uses the same bitwise operations as other languages to iteratively construct the number, checking for divisibility by mod 5.
Time Complexity: O(n).
Space Complexity: O(n) to keep the results list.
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).
function prefixesDivBy5(nums: number[]): boolean[] {
const ans: boolean[] = [];
let x = 0;
for (const v of nums) {
x = ((x << 1) | v) % 5;
ans.push(x === 0);
}
return ans;
}func prefixesDivBy5(nums []int) (ans []bool) {
x := 0
for _, v := range nums {
x = (x<<1 | v) % 5
ans = append(ans, x == 0)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Binary Construction | Time Complexity: O(n). |
| Using Bitwise Operations | Time Complexity: O(n). |
| Simulation | – |
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. |
Frequently asked questions
Is Binary Prefix Divisible By 5 easy or hard?
Binary Prefix Divisible By 5 is classified as an Easy problem on LeetCode. The challenge is recognizing that storing the full binary number is unnecessary. Using modular arithmetic to track only the remainder reduces the problem to a simple linear scan.
Binary Prefix Divisible By 5 Python/Java solution
In Python or Java, iterate through the array and keep a remainder variable. Update it with remainder = (remainder * 2 + bit) % 5 and append whether the remainder equals 0. The same logic works in C++, JavaScript, and C# with identical O(n) time complexity.
How to solve Binary Prefix Divisible By 5 in O(n)?
Iterate through the binary array while maintaining the current remainder modulo 5. For each bit, update the remainder with (remainder * 2 + bit) % 5 or ((remainder << 1) | bit) % 5. If the remainder equals zero, append true to the result; otherwise append false. This processes all prefixes in a single pass.
What is the best approach for Binary Prefix Divisible By 5?
The optimal approach tracks the remainder of the current binary prefix modulo 5 while iterating through the array. Update it using (remainder * 2 + bit) % 5 for each new bit. If the remainder becomes 0, the prefix is divisible by 5. This method runs in O(n) time and uses O(1) extra space.
Is Binary Prefix Divisible By 5 asked at Google/Amazon/Meta?
Binary prefix and modular arithmetic problems appear frequently in interviews at large tech companies because they test number representation and streaming computation. Variations involving binary prefixes, divisibility, or remainder tracking have appeared in coding rounds at companies like Amazon and Google.
What data structure is used in Binary Prefix Divisible By 5?
The core data structure is a simple array traversal. The algorithm maintains a running integer remainder while iterating through the binary array. Bit manipulation or modular arithmetic is applied at each step to compute divisibility efficiently.
What is the time complexity of Binary Prefix Divisible By 5?
The optimal algorithm runs in O(n) time because each element of the binary array is processed once. Every step performs constant-time arithmetic or bit operations. Space complexity is O(1) excluding the output array since only a small remainder variable is maintained.