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 users
@taran_1407 @cubefreak777 @ashutosh450 @l_returns @vijju123 @nishant403 @anshugarg12 @ssjgz @ayush_2407