[Solution] Equal by XORing solution codechef

Equal by XORing solution codechef – JJ has three integers AABB, and NN. He can apply the following operation on AA:

• Select an integer XX such that 1X<N1≤X<N and set A:=AXA:=A⊕X. (Here,  denotes the bitwise XOR operation.)

[Solution] Equal by XORing solution codechef

JJ wants to make AA equal to BB.
Determine the minimum number of operations required to do so. Print 1−1 if it is not possible.

Input Format

• The first line contains a single integer TT — the number of test cases. Then the test cases follow.
• The first and only line of each test case contains three integers AABB, and NN — the parameters mentioned in the statement.

Output Format

For each test case, output the minimum number of operations required to make AA equal to BB. Output 1−1 if it is not possible to do so.

[Solution] Equal by XORing solution codechef

• 1T10001≤T≤1000
• 0A,B<2300≤A,B<230
• 1N2301≤N≤230

• Subtask 1 (30 points): NN is a power of 22.
• Subtask 2 (70 points): Original Constraints.

Sample Input 1

3
5 5 2
3 7 8
8 11 1


[Solution] Equal by XORing solution codechef

0
1
-1


Explanation

• Test Case 11: AA is already equal to BB. Hence we do not need to perform any operation.
• Test Case 22: We can perform the operation with X=4X=4 which is <8<8. Therefore A=34=7A=3⊕4=7. Thus, only one operation is required.
• Test Case 33: We can show that it is not possible to make AA equal to BB.

Sample Input 2

2
24 27 3
4 5 1000


[Solution] Equal by XORing solution codechef

2
1


Explanation

Note that the above sample case belongs to subtask 22.

• Test Case 1: We can first perform the operation with X=1X=1 which is <3<3. Therefore A=241=25A=24⊕1=25. Then we can perform the operation with X=2X=2 which is <3<3. Therefore A=252=27A=25⊕2=27. Therefore we can make AA equal to BB in 22 operations. It can be shown that it is not possible to do this in less than 22 operations.