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$
5
  • 1
    $\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
0
$\begingroup$

As noted in the comments, a summation sign is missing.

There are $20$ conditions to fulfil, corresponding to each of the $20$ bits being $0$, and we're looking for the groups that fulfil all of these conditions. The number $x$ represents a subset of the conditions that are violated, namely the subset corresponding to the bits set in $x$. To form a bitwise AND result that violates the conditions represented by $x$, we can AND any number of elements $a_i$ that satisfy $a\operatorname{\&}x=x$, since then and only then will the bits in $x$ be set in the result. There are $2^{f(x)}$ groups of such elements. Thus, by inclusion–exclusion there are

$$ \sum_x(-1)^{g(x)}\cdot2^{f(x)}\;, $$

admissible groups, where $x$ runs over all natural numbers with up to $20$ bits.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.