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
C++ 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(std::vector<int> batch) {
}Worked examples
| Call | Result |
|---|---|
loneReading(std::vector<int>{4, 1, 2, 1, 2}) | 4 |
loneReading(std::vector<int>{2, 2, 1}) | 1 |
loneReading(std::vector<int>{7}) | 7 |
loneReading(std::vector<int>{}) | 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 C++
int loneReading(std::vector<int> batch) {
int lone = 0;
for (int reading : batch) lone ^= reading;
return lone;
}