PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Jeevan Jyot Singh
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra
DIFFICULTY:
1626
PREREQUISITES:
None
PROBLEM:
You are given two integers N and K. Find number of ordered triplets (A, B, C) that satisfy the following conditions:
- 0 \le A, B, C \lt 2^N
- A, B and C are distinct
- A \oplus B \oplus C = K
Here, \oplus denotes the bitwise XOR operation.
EXPLANATION:
Observation 1: Given any number A \;(\leq 2^N), we can always select two numbers B and C such that their XOR is K.
This is because for each bit of A, we can set bits of B and C accordingly such that the final XOR of the three is equal to the bit of K.
Let’s have bit representation of a number X be as:
Now for K if at any position i (going from right to left), its bit would be K_i. Lets take two cases:
-
K_i = 1:
- For A_i = 1: To make final XOR as 1, (B_i,C_i) could be either (1,1) or (0,0)
- For A_i = 0: To make final XOR as 1, (B_i,C_i) could be either (1,0) or (0,1)
-
K_i = 0:
- For A_i = 1: To make final XOR as 0, (B_i,C_i) could be either (1,0) or (0,1)
- For A_i = 0: To make final XOR as 0, (B_i,C_i) could be either (1,1) or (0,0)
Observation 2: None of the numbers can be K since then the other two numbers would become equal to each other.
Thus now for selecting A we would have 2^N - 1 options. As for B and C, for each bit position of A, we would have 2 ways of selecting bits of B and C. Among all the possible selections of B and C, there shall be 1 case where B is equal to A and 1 case where C will be equal to A. Thus after subtracting these cases we will have 2^N - 2 ways of selecting B and C. Thus our final answer would be:
TIME COMPLEXITY:
O(logN), for each test case.
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution