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
public int LoneReading(List<int> batch) {
}Worked examples
| Call | Result |
|---|---|
LoneReading(new List<int> { 4, 1, 2, 1, 2 }) | 4 |
LoneReading(new List<int> { 2, 2, 1 }) | 1 |
LoneReading(new List<int> { 7 }) | 7 |
LoneReading(new List<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#
public int LoneReading(List<int> batch) {
int lone = 0;
foreach (var reading in batch) lone ^= reading;
return lone;
}