360. Unpaired in Order
A ticket scanner reads a sorted list of seat codes. Every code appears exactly twice, one for each of the two door scans, except one code that was scanned only once because a door jammed. Equal codes are always next to each other since the list is sorted.
Given the sorted array nums, return the code that appears only once. A solution that reads every entry or uses a hash set is too slow and uses too much memory for this problem: it has to run in O(log n) time and O(1) extra space. The array always has an odd length.
Example 1
- Input:
- nums = [1,1,2,3,3]
- Output:
- 2
- Explanation:
Every code is scanned twice except 2.
Example 2
- Input:
- nums = [5,8,8,9,9,12,12]
- Output:
- 5
- Explanation:
The code 5 appears only once.
Constraints
1 ≤ nums.length ≤ 106, and nums.length is odd
0 ≤ nums[i] ≤ 109nums is sorted; exactly one value appears once and every other value appears exactly twice.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(log n)
- Space
- O(1)