The reading that only came once
Every sensor reports twice except one, whose second report went missing. Find the reading with no partner, without keeping the whole batch in memory.
- Every value appears exactly twice, except one that appears once.
- The batch is in no particular order.
- Return the value that appears once.
- An empty batch returns 0.
loneReading(batch: list<int>) → int
Java needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int loneReading(List<Integer> batch) {
}Worked examples
| Call | Result |
|---|---|
loneReading(Main.<Integer>ls(4, 1, 2, 1, 2)) | 4 |
loneReading(Main.<Integer>ls(2, 2, 1)) | 1 |
loneReading(Main.<Integer>ls(7)) | 7 |
loneReading(Main.<Integer>ls()) | 0 |
Hint
A value exclusive-or’d with itself is zero, and order does not matter. Fold the whole batch together with xor and the pairs cancel out.
Reference solution in Java
int loneReading(List<Integer> batch) {
int lone = 0;
for (int reading : batch) lone ^= reading;
return lone;
}