2
$\begingroup$

We have $n$ non-negative integers $a_1, a_2, \dots, a_n$. We will call a sequence of indexes $i_1, i_2, \dots, i_k$ such that $1\le i_1 < i_2 < \dots< i_k\le n$ a group of size $k$.

How many groups exists such that

$$a_{i_1}\mathbin{\&} a_{i_2}\mathbin{\&}\ldots\mathbin{\&} a_{i_k} = 0\;,$$

where $1\le k\le n$.

Operation $x\mathbin{\&} y$ denotes bitwise AND operation of two numbers.

Approach:

Use inclusion-exclusion principle in this problem.

Let $f(x)$ be the count of numbers $i$ where $A_i\mathbin{\&}x = x$.

Let $g(x)$ be the number of $1$s in the binary respresentation of $x$. Then the answer is equal to

$$(-1)^{g(x)}\cdot 2^{f(x)}$$

But I could not understand the correctness and working intuition of this.

For calculating f(x) if Number are in range 0 to 10^6 so bit required to represent them is 20.

 for(int i=0;i<20;i++) {
            for(int j=0;j<(1<<20);j++) {
                if(0 == (j & (1<<i))) {
                    f[j | (1<<i)] += f[j];
                }
            }
        }

Please Help.

For Example:

0 1 2 3

Ans: 10

$\endgroup$
  • $\begingroup$ Since $A_i$ is undefined, in the definition of $f(x)$ should it be $a_k\mathbin{\&}x=x$ instead of $A_i\mathbin{\&}x=x$? The expression $(-1)^{g(x)}\cdot2^{f(x)}$ is meaningless until you tell us what $x$ is, and I suspect that you’ve left out a summation sign. Finally, by my count the correct answer for $0,1,2,3$ is $9$, not $10$: there are $2^3=8$ groups that include $0$, and the only other solution is $1\mathbin{\&}2=0$. $\endgroup$ – Brian M. Scott Jul 24 '15 at 9:45
  • $\begingroup$ summation should be there my mistake !!!! But answer is 10 8 group with zero one group with 1 and 2 and finally ` 1 and 2 and 3` $\endgroup$ – Sunny Jul 24 '15 at 9:56
  • $\begingroup$ @BrianM.Scott can you explain me the mathematics behind it , it would help me a lot $\endgroup$ – Sunny Jul 24 '15 at 9:58
  • $\begingroup$ I haven’t quite figured out what’s going on. It would help if you could say what values of $x$ the summation is taken over. $\endgroup$ – Brian M. Scott Jul 24 '15 at 10:02
  • $\begingroup$ @BrianM.Scott updated it $\endgroup$ – Sunny Jul 24 '15 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.