Lone Sensor Reading
EasyBit ManipulationFree
Problem
A pair of redundant sensors reports every reading twice, so the log readings normally holds each value exactly two times. One reading lost its twin in transit and appears only once.
Return that unpaired reading. Use O(1) extra memory.
Example 1
- Input:
- readings = [4, 1, 2, 1, 2]
- Output:
- 4
1 and 2 each appear twice; 4 appears once.
Example 2
- Input:
- readings = [7]
- Output:
- 7
Example 3
- Input:
- readings = [3, 9, 3]
- Output:
- 9
Constraints
- 1 ≤ readings.length ≤ 3 · 10^4 (always odd)
- 0 ≤ readings[i] < 2^31
- Exactly one value appears once; every other value appears exactly twice.
Hint
Show the first hint
Is there an operation where combining a value with itself gives a neutral result?
Walkthrough
How to approach it
01Clarify before coding
- Can the lone value be 0? Yes, and the answer is then 0; the XOR approach handles it naturally.
- Are twins guaranteed to appear exactly twice, not three or four times? Exactly twice: that is what makes XOR cancellation work.
- Is the log sorted? No, twins can be anywhere.
02Brute force
Count occurrences with a hash map and return the value whose count is 1, or sort and scan adjacent pairs.
Cost: Hash map: O(n) time but O(n) extra memory. Sorting: O(n log n) time. Both miss the O(1)-memory requirement or the linear time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.