Loading...
Loading...
Loading...
A hostel mess gives every student two meal tokens with the same ID, one for lunch and one for dinner. At night the manager counts the returned tokens. Exactly two different students returned only one token each.
Given the returned token IDs in any order, print the two IDs that appear only once, smaller one first.
Example 1
Input
6 1 2 1 3 2 5
Output
3 5
1 and 2 appear twice. 3 and 5 appear once.
Example 2
Input
4 6 9 9 4
Output
4 6
4 and 6 differ first in bit 1 (value 2), not in bit 0.
Try the problem first. Open one hint at a time.
XOR of all the IDs cancels every pair. What is left is x ^ y, where x and y are the two answers.
x and y are different, so x ^ y has at least one 1 bit. At that bit, x and y differ.
Pick the lowest 1 bit with diff & -diff. Split all IDs into two groups by that bit and XOR each group on its own.
Pairs land in the same group and cancel, so each group leaves exactly one of the answers.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor