1018. Binary Prefix Divisible By 5
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 47.8%
Problem Breakdown
The problem requires us to determine if each prefix of a binary number formed by an array of 0s and 1s is divisible by 5. The input is an array A where each element is either 0 or 1. The output should be a list of booleans, where each boolean indicates whether the binary number formed from the start of the array up to that index is divisible by 5.
Inputs:
- An array
Aof integers (0s and 1s).
Outputs:
- A list of booleans indicating divisibility by 5 for each prefix.
Implicit Constraints:
- The length of the array can be up to 30,000.
- Each element in the array is either 0 or 1.
- Edge cases include an empty array (though the problem specifies
1 <= A.length).
Intuition
A brute-force approach would involve converting each prefix of the array into a binary number and checking if it’s divisible by 5. However, this approach would be inefficient due to the large size of the input array and the repeated conversion of binary numbers.
The key insight is to use modular arithmetic to keep track of the current binary number modulo 5 as we iterate through the array. This way, we avoid converting the entire prefix each time and only need to maintain a running total that we update with each new bit.
Approach
- Initialize an empty list
answerto store the results. - Initialize a variable
current_numberto 0 to keep track of the current binary number modulo 5. - Iterate through each element in the array
A.- Update
current_numberby shifting it left (equivalent to multiplying by 2) and adding the current bit, then take modulo 5. - Append
Truetoanswerifcurrent_numberis 0 (i.e., divisible by 5), otherwise appendFalse.
- Update
- Return the list
answer.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array
A. We iterate through the array once. - Space Complexity: O(1) for the additional variables used, excluding the space required for the output list.
Solution
def prefixesDivBy5(A):
answer = []
current_number = 0
for bit in A:
current_number = (current_number * 2 + bit) % 5
answer.append(current_number == 0)
return answer
Edge Cases Handled
- Empty Array: The problem specifies
1 <= A.length, so this case is not applicable. - All Zeros: The binary number formed will always be divisible by 5, resulting in a list of all
Truevalues. - All Ones: The binary number will grow rapidly, but the modulo operation ensures we only keep track of the remainder, preventing overflow.