Hii Chefs,
Recently I faced a problem in which I have to find number of triplets in array such that:
-
i < j <k
-
( arr[i] | arr[j] | arr[k]) & X = ( arr[i] | arr[j] | arr[k])
Where,
-
| => bitiwise OR
-
& => bitwise AND
You are given q queries in which each query contains integer X. Count triplets which satisfy above conditions for each query X.
I thought we can use bittrie for this problem but couldn’t solve it as I was new to this concept. Can anyone explain approach for this problem with explanation?
Examples
Input:
N = 4 ,array = [1,2,4,8]
Q=2 , queries = [14,15]
Output:
[1,4]
Input:
array = [6,2,7,4] N=4
Queries = [6,7,14]
Output:
[1,4,1]
Constraints:
1 <=N <= 10^5
1 <= Array[i] <= 10^6
1 <= Q<= 10^5
1 <= queries[i] <= 10^6