# Another OR Related Problem

I recently appeared for a contest and many questions were asked. I could solve all but 1.

The question is suppose you are given an array A consisting of N elements
Then form a new Array B, such that it contains binary or of elements from Al | Al+1 | . . | Ar
for all 1 <= l <= r <= N

for example given Array is A = [1, 2, 4]
then B contains = [1, 2, 4, 1|2, 2|4, 1|2|4] = [1, 2, 4, 3, 6, 7]

Given a list of Q Queries each query denoted a number K , we have to find the K’th smallest number in B

Lets say the queries are [2, 5]
then answer would be a list = [2, 6] // 2nd and 5th smallest element respectively

Assume all arrays are 1 indexed

Constraints
1 <= N <= 105
1 <= Q <= 105
1 <= A[i] <= 109

Time Limit: 4.sec

can anyone tell me how one could approach this

PS: I tried this article here but was not able to make much progress on finding rank of a number in subarray or

UPD: I HAVE SOLVED THE PROBLEM.

“Tagging most frequent posters”

• Next time, don’t.
Edit: I was tagged in the previous revision of the post
1 Like

Since there are only 30 bits in the numbers, the OR won’t change more than 30 times if you start from a certain index. So array B will only have Nlog(maxA) elements.

There are multiple ways to efficiently find those elements, for example, segtree+descent or sparse table+binary search.

2 Likes

Yeah I removed you from tag. Didn’t knew it would be a bother. Anyway I would try what u said below and see if i could make it work. Thanks anyway

I did see your video on segment tree and descent but am still confused how to do this. would you please explain in a bit more detail

Send the solution @roushan_17

can you share the solution