https://leetcode.com/problems/binary-prefix-divisible-by-5/
Given an array
A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)
Return a list of booleans
answer, where answer[i] is true if and only if N_i is divisible by 5.
Example 1:
Input: [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: [1,1,1] Output: [false,false,false]
Example 3:
Input: [0,1,1,1,1,1] Output: [true,false,false,false,true,false]
Example 4:
Input: [1,1,1,0,1] Output: [false,false,false,false,false]
Note:
1 <= A.length <= 30000A[i]is0or1
curr keeping track of decimal representation so far. When scanning from right, if we multiply curr by 2, it will shift all the bits in curr to left to make place for the incoming digit i. That way, we are reusing the computations. We are not interested in the actual number, so to avoid overflow, we can subtract 5 as many times as possible (i.e. modulo by 5) and still validate if it is divisible by 5.public List<Boolean> prefixesDivBy5(int[] A) {
List<Boolean> res = new ArrayList<>();
int curr = 0;
for(int i : A){
curr = 2*curr+i;
curr %= 5;
res.add(curr == 0);
}
return res;
}
Since A includes only
0s and 1s, we can imitate binary operations. public List<Boolean> prefixesDivBy5(int[] A) {
int k = 0;
List<Boolean> ans = new ArrayList<>();
for (int a : A) {
k = (k << 1 | a) % 5;
ans.add(k == 0);
}
return ans;
}public List<Boolean> prefixesDivBy5(int[] A) {
List<Boolean> list = new ArrayList<>();
int remainder = 0;
for(int bit : A) {
if (bit == 1)
remainder = (remainder * 2 + 1) % 5;
if (bit == 0)
remainder = (remainder * 2) % 5;
if(remainder%5==0) {
list.add(true);
} else {
list.add(false);
}
}
return list;
} def prefixesDivBy5(self, A):
for i in xrange(1, len(A)):
A[i] += A[i - 1] * 2 % 5
return [a % 5 == 0 for a in A]
For anyone wondering why you need to do the % 5 calculation twice, in short because it's vastly more efficient for both time and space complexity. The calculation is still 100% accurate, but you are not taking up additional space in memory by holding the entirety of the numbers or taking the extra time to then make calculations with the larger numbers.
Case in point (code and complexities in python3):
def prefixesDivBy5(self, A):
for i in range(1, len(A)):
A[i] += A[i - 1] * 2
return [x % 5 == 0 for x in A]
had a runtime of 328 ms, with memory usage 78.6 MB, whereas
def prefixesDivBy5(self, A):
for i in range(1, len(A)):
A[i] += A[i - 1] * 2 % 5
return [x % 5 == 0 for x in A]
had a runtime of only 116 ms and used only 16.3 MB space
