[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.)

Table of Contents

[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

Subtasks

  • 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.

For Solution

Click Here

Leave a Comment