PROBLEM LINK:Author: Misha Chorniy DIFFICULTYEASY PREREQUISITENONE PROBLEMGiven an array of N integer. Calculate how many contiguos subarray that have the ORsum larger or equal to K. SOLUTIONFor each position i we will find the smallest j ≥ i such that the ORsum of A[i…j] larger than or equal to K then we would know that there is N  j + 1 valid subarray starting at i. Notice that with i fixed ORsum of A[i…j] increses when j increases (ORsum increases when we add more numbers). With that we can use binary search with each i to find j If we can calculate ORsum of A[i…j] efficiently (one way to calculate ORsum 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 ORsum of A[i…j] larger than or equal to K. The ORsum between i and j can be maintained by keeping the number of bit 1 at each position among all numbers in the subarray 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 ORsum. Update the cnt[] or calculate ORsum 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])). AUTHOR'S AND TESTER'S SOLUTIONS:asked 18 Dec '16, 23:05

@admin setter and tester solution is not visible. Can you please explain this line : "The ORsum between i and j can be maintained by keeping the number of bit 1 at each position among all numbers in the subarray A[i…j]." ? answered 19 Dec '16, 01:12
if any number in A[i...j] has a set bit at position k then ORsum 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 ORsum. You can look at this solution https://www.codechef.com/viewsolution/12301785 that I wrote after competition
(19 Dec '16, 02:29)

in the line "cnt[i] is the the numbers of numbers in A[i…j] that hava 1 at the ith bit." , use of i seems ambiguos. answered 19 Dec '16, 02:24
What do you feel is the ambiguity. Did you understand the logic. You need help in understanding logic or implementation.
(19 Dec '16, 09:02)
@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].
(19 Dec '16, 14:47)

I did using a sparse table of almost similar complexity O(n log n ) , Code in Python : https://www.codechef.com/viewsolution/12299242 answered 19 Dec '16, 09:25

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: https://www.codechef.com/viewsolution/12298985 answered 19 Dec '16, 10:23

The segment tree approach is O(nlognlogn) which really seemed a overkill. answered 19 Dec '16, 12:01

I tried to do it using segment trees but i'm missing out somewhere, can anybody help? http://ideone.com/OEiuJF here is the code answered 19 Dec '16, 12:53

can anyone tell me what is wrong with this solution i am using sliding window technique it passes all given test cases https://www.codechef.com/viewsolution/12302833 answered 19 Dec '16, 13:35

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 :) answered 21 Dec '16, 08:36
you can refer this solution.. https://www.codechef.com/viewsolution/12936619 let me know if any part you didn't understand!!
(26 Feb '17, 00:16)

It could be done using 2 pointer concept and segment tree in O(n log n). here is the code https://www.codechef.com/viewsolution/16744917
link
This answer is marked "community wiki".
answered 03 Jan '18, 22:11

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 answered 19 May '18, 12:46
