PROBLEM LINK:
Author: Shreyasi Verma
Tester: Shivani Srivastava
Editorialist: Kaushambi Gujral
DIFFICULTY:
EASY
PREREQUISITES:
Bit Manipulation
PROBLEM:
Given are ‘n’ crackers where each type of cracker appears exactly twice except the ‘Special Cracker’
QUICK EXPLANATION:
The ‘Special Cracker’ can easily be spotted out by using XOR.
EXPLANATION:
As there are ‘n’ crackers, and we know that each type of cracker will appear twice except the ‘Special Cracker’, we probably would use the concept of XOR to handle this.
Quickly brush up the concept using the following:-
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
Consider the example with the following types of crackers:
2 2 3
Simply calculate XOR of all the elements.
2 in binary is 10, where as 3 is 11. The computations would be bit-wise.
Step 1: 2 ^ 2 = 0
Step 2: 0 ^ 3 = 3
Thus, 3 is the answer. If you look at the input, it is quite clear that type-3 cracker is the ‘Special Cracker’!
AUTHOR’S AND TESTER’S SOLUTIONS:
The solution can be found here.