Interview Bit Problem

Given an integer N. Count all pairs of integers from 0<=x,y<2^N , such that OR(x,y) = XOR(x,y).
By running bruteforce, I found out that the answer is 3^N, but I have no proof of my solution. Can someone help with the proof?

Because for every n spaces, there are 3 options
00,01,10 because in case of 11 or and xor is different. So, 3^n.

1 Like

2**N means there are N bits. If you see the above conditions is only possible in these -
0 1
1 0
0 0
so for each N bit we have three options

1 Like

You can think like you need to count the pairs where the and of them is zero.
As if xor(x,y) == or(x,y)
It means in their binary representation
0^0 = 0 , 0|0 = 0
1^0 = 1 , 1|0 = 1
0^1 = 1 , 0|1 = 1
1^1 = 0 , 1|1 = 1
Now we can say if x&y is not equal to zero then at some position we have set bits in x and y, and hence if we have set bits at a position in both the nos. then their xor and or won’t be equal. So we need to find out the pairs where the x&y == 0 to get the answer for xor(x,y) == or(x,y).

1 Like

If someone’s looking for a more rigorous proof,
So let’s make a few important observations first (which I’m pretty sure that you might have noticed already) :
1. If x=1 then the value of y is bound to be 0 (\because 1\oplus0=1|0, 1\oplus1\neq1|1))
2. If x=0 then the value of y can be 0 or 1.
Now firstly we will try to fix our x and then find all the y's which satisfy this equation. For example, let our x has the binary representation as follows x=11001.
So from observation (1) we can say that all the bits which are set in x will be unset in y. Hence in this case y will be of the form y=00--0.
From observation (2) we can say that for each unset bit in x we have 2 options i.e. we can either have the corresponding bits in y as 0 or 1.
So for any x if the number of unset bits in x is u(x) then number of y's will be 2^{u(x)}.
Hence final S=\sum_{i=0}^{2^N}2^{u(i)} where u(i) is the number of unset bits in i.
Now if we use the contribution technique for each 1\le u \le N then each 2^u we will have a contribution of \binom{N}{u} (since we can have any u bits out of N as unset) i.e.
S=\sum_{u=0}^{N}\binom{N}{u}2^{u} \implies S=(1+2)^N=3^N

5 Likes

Thank you guys🙌

1 Like