OR queries

general
,
1

Can anyone help regarding the problem asked in hackerearth hiring challenge (challenge closed now), problem statement is as follows -

You are given the following:

  • An array A consisting of N positive integers
  • Q queries of the form L, R, M

In each query, consider the array B = (A[L], A[L+1], A[L+2],…, A[R]) which means B is a subarray of A and contains elements of A present between the indices L and R. Consider all subsequences of this array B of size M.

Task

Determine the sum of Bitwise OR of all these subsequences. Bitwise OR of the empty subsequence is 0. If there is no subsequence of length M, print 0.

2

What are the constraints on A_i ?

3

0 <= Ai <= 10^9
0 <= M <= 10^6

1 Like
4

So here’s what I’d do:
for any query [L,R,M]
let N=R-L+1
if N<M answer is straight away 0.
So it’s quite trivial to see that there’d be \binom{N}{M} different subsequences of size M when elements are chosen from [L,R]. Now for each bit i count the number of subsequences out of the \binom{N}{M} subsequences which have their ith bit set, let’s say this value for bit i is C_i.
We can find C_i's by precomputing a prefix sum table P_{i,j} where:
P_{i,j}=\sum_{j=1}^nB_j, here B_j is a binary variable which is 1 if ith bit of A_j is unset else zero.
So we can compute the number of elements that have their ith bit unset in a given range using our precomputed prefix table by ,
U_{L,R}=P_{i,R}-P_{i,L-1}
Hence, C_i=\binom{N}{M}-\binom{U_{L,R}}{M}
So final answer for any range [l,r] would just be equal to S=\sum_{i=1}^{30}2^iC_i
PS: I’ve assumed that \binom{N}{r}=0 if N<r

3 Likes
6

@cubefreak777
Can you elaborate below with an example
for each bit i count the number of subsequences out of the (N,M) subsequences which have their ith bit set.

7

Suppose we have A=[12,14,13,9,5,10,11] and for some query say L=2,R=5,M=2. So we’re analyzing this subarray B

A=[12,\underbrace{14,13,9,5}_\text{B},10,11]
B=[14,13,9,5],N=R-L+1=5-2+1=4

All Valid subsequences of length M=2 are : [14,13],[14,9],[14,5],[13,9],[13,5],[9,5]
i.e. we have {N \choose M}={4\choose2}=6 subsequences in total
let’s say we want to count the number of subsequences that have their bitwise OR’s 1st bit set.
[14,13] \implies (14|13)=15=11\textbf{1}1 \implies set
[14,9] \implies (14|9)=15=11\textbf{1}1 \implies set
[14,5] \implies (14|5)=15=11\textbf{1}1 \implies set
[13,9] \implies (13|9)=13=11\textbf{0}1 \implies unset
[13,5] \implies (13|5)=13=11\textbf{0}1 \implies unset
[9,5] \implies (9|5)=13=11\textbf{0}1 \implies unset
So out of the \binom{N}{M}=\binom{4}{2}=6 subsequences we have only 3 subsequences which have their 1st bit set. Similarly we want to count for all bits. i.e. 0,2,3...30

4 Likes
8

@cubefreak777 , thank you!

1 Like
9

Thanks Man. I was thinking the same but was confused related combining prefixsum and subsequences. so asked for example.

1 Like