Given an array of N integer. Calculate how many contiguos sub-array that have the OR-sum larger or equal to K.
SOLUTION
For each position i we will find the smallest j ≥ i such that the OR-sum of A[i…j] larger than or equal to K then we would know that there is N - j + 1 valid sub-array starting at i. Notice that with i fixed OR-sum of A[i…j] increses when j increases (OR-sum increases when we add more numbers). With that we can use binary search with each i to find j If we can calculate OR-sum of A[i…j] efficiently (one way to calculate OR-sum of any A[i…j] is building the segment tree).
The mentioned solution seems to be overkill with this easy problem not to say that it doesn’t give the best run time. We can avoid binary search and use the two pointer technique where one pointer is the position of i and the other one is j. With each i we try to increase j until we got the OR-sum of A[i…j] larger than or equal to K. The OR-sum between i and j can be maintained by keeping the number of bit 1 at each position among all numbers in the sub-array A[i…j]. Basically we maintain an array cnt[0…31] where cnt[i] is the the numbers of numbers in A[i…j] that hava 1 at the ith bit.
All we do is increase i or j, update the cnt[] array and calculate the OR-sum. Update the cnt[] or calculate OR-sum from cnt[] both take O(32) (which is corresponding to the number of bits the max value of A[i]). So the total complexity would be O(N×log(max A[i])).
@admin setter and tester solution is not visible. Can you please explain this line : “The OR-sum between i and j can be maintained by keeping the number of bit 1 at each position among all numbers in the sub-array A[i…j].” ?
Can be done using segment tree and binary search in O(nlognlogn). For every position i, we can binary search the minimum index greater than i for which the subarray [i,index] have OR value greater than K. For finding out OR values of different segments, we can use seg trees.
Code: CodeChef: Practical coding for everyone
Can anyone please tell, that for each number in the array how can I find efficiently which are the set bits(1) in the binary representation of that number , so that we can store 1 in those positions of the cnt[] array.
P.S. I’m a not quite used to bit manipulation in problems
can someone explain for the given example n=3,k=3
and value are 1,2,3 the output is 4 but i am getting sub arrays as 5 i.e.,
(1,2),(1,3),(2,3),(1,2,3),(3)=5
if any number in A[i…j] has a set bit at position k then OR-sum of this subarray will have kth bit set, so by maintaining the number of 1s at each position for any subarray using cnt array as mentioned above you can calculate the OR-sum. You can look at this solution CodeChef: Practical coding for everyone that I wrote after competition
@arpit728 I understood the logic and have already solved the problem. The statement is ambiguos because i represent two different things in that line i.e. i represents starting point of subarray A[i…j] and also it presents the position of bit in cnt[i].