This is a perfect example of que which can destroy ur confidence.
om shanti 
29 Likes
Observation 1:
3 * 3 - 3 = 6
Observation 2:
7 * 7 - 7 = 42
Observation 3:
511 * 511 - 511 = 260610
Observation 4:
For N and K the answer will be
(2^N - 1)(2^N - 1) - (2^N - 1)
9 Likes
Yet another formula-
(2^N C 3 / 2^ N) * 6
i.e
number of ways to choose 3 numbers from entire possible numbers/ all possible numbers * number of ways to arrange 3 numbers
1 Like
Thus now for selecting A we would have 2^N-1 options.
And how did it got proved?
1 Like
Interesting.
I went thinking like this. If a bit in K is 0, then I have 4 options for the same bit in A,B,C \rightarrow 000, 011, 101, 110. If a bit in K is 1, then I also have 4 options 111, 100, 010, 001.
All triplets that xor to K is then 4^{n}. Of course, the task says numbers in a triplet need to be distinct. So I subtract all cases when 2 numbers are the same, which is 3\cdot (2^{n}-1) \rightarrow there are 2^n possible numbers, and if two are the same and third one is K (without a loss of generality A = B = x and C=K) I have 2^n-1 choices for x (multiplied by 3 because there are 3 options for which number is K). I also want to exclude (K,K,K) from the final count so I will subtract 1.
4^n-3\cdot(2^n-1)-1
18 Likes
//6 = 2 multiply 3 n=2 1<<2 =4 (4-1) multiply (4-2)
//42=6 multiply 7 n=3 1<<3=8 (8-1) multiply(8-2)
//260610=510 multiply 511 n=9 1<<9=512 (512-1 ) multiply (512-2)
https://www.codechef.com/viewsolution/67419259
I got amazed by the answer i got which didn’t depend upon k at all. Great question.
how did you calculate when two numbers are same can you please elaborate more ?
Lets see
making b == c → (for unset bit we have 0 11 case + 0 00)
(for set bit we have 1 11 case + 1 00)
see the last two bit remians the same for b and c
ways: (2^(set_bit count) )*(2^( n - set_bit count))
similary for a==b and a==c
Now we have to add two case which is reduces 3 time (a==b==c)
ans = 4^n - (2^n)*3 + 2
2 Likes
Total number of choices 2^n from which you cant take k ( as the other two will become the same which is not allowed )
So total choice = 2^n - 1
1 Like
A \oplus B \oplus C = K, if A = B = x, then A \oplus B = 0 \implies 0 \oplus C=K \implies C=K.
How many triplets have the form (x, x, K)?
If x \neq K, then out of 2^n numbers (in range 0 to 2^n-1, there is 2^n numbers) you can choose 2^n-1 for x (if you use all numbers but K). If you change the choice for which number is K, A=C=x, B=K, then that’s another 2^n-1 extra triplets to remove and same is the case for B=C=x, A=K.
In total there is 3 \cdot (2^n -1) cases where one number is K and others are equal.
K \oplus K \oplus K = K. When we counted 3 \cdot (2^n - 1) we explicitly avoided (K,K,K), by not choosing x = K. Therefore, we need to subtract 1 to remove (K, K, K) from the total count 4^n.
3 Likes
Thanks buddy.
thanks
I also went with thinking… but couldn’t exclude 2 equal numbers and all 3 equal numbers
Now i understood… nyc explaination tnks bhai 
who can’t get it…
4^n is total number of (distinct) triplates, whose xor is k
if 2 nums are same than thier xor will be zero and 3rd number will have to be k
a==b then c=k ,…,… (2^n-1 ways)
a==c then b=k ,…,… (2^n-1 ways)
b==c then a=k ,…,… (2^n-1 ways)
a=b=c = k ,…,… (1 ways)
1 Like
Why we are diving it by all possible values ? This I did not get. Please help!
The value of A can range from [0 - 2^n) (2^n is not included), so we can say we have 2^n choices. Out of them A cannot be equal to K because if A==K then B should we equal to C. so 2^n - 1 choices!
Hope you understood!
I came up with the solution
4^n - 3*2^n + 2
- for every bit, be it 1 or 0, we have 4 choices,
eg) for K’s i’th bit is 1 lets say, so i’th bit in {a,b,c} could be {1,1,1}, {1,0,0}, {0,1,0}, {0,0,1}.
if K’s i’th bit is 0, then {a,b,c} could be {1,1,0}, {1,0,1}, {0,1,1}, {0,0,0}.
Hence 4 options for every bit, thus the 4^n.
- We cannot have duplicates, for any pair in {a,b,c}, we can have 2^n duplicates possible.
eg) for K’s i’th bit is 1 lets say, so i’th bit in {a,b,c} could be {1,1,1}, {1,0,0}, {0,1,0}, {0,0,1}.
for a to be same as b, we see {1,1,1} and {0,0,0} has a = b, i.e 2 in those 4.
we can make pairing a,b or b,c or c,a so we subtract 3 * 2^n
- As we have decreased a=b, b=c, c=a cases, we have removed the case a=b=c total of three times, we only needed to removed it once. so we add the case a=b=c case twice.
every bit has only 1 case where a=b=c, so we add 2 * (1^n) .
Final answer = 4^n - 3 * 2^n + 2
1 Like
OSM 
hey @mankesh nice explaination
I was stuck on how to exclude same numbers. You cleared it. That’s some quality explanation.