The odd one out in sorted pairs
Find the one value that appears once in a sorted list of pairs, by checking whether pairs still line up on even positions. About 14 minutes.
Pairs line up until they don't
A sorted list has every value twice, except one that appears once. For example 1, 1, 2, 3, 3, 4, 4, 8, 8 has a single 2. The length is always odd.
Look at where pairs sit. Before the single value, the pairs occupy positions (0, 1), (2, 3), (4, 5): each pair starts at an even position. The single value takes one slot alone, so after it the pairs start at odd positions. Finding where that changes finds the single value.
if mid % 2 == 1:
mid -= 1 # line up on an even indexThe middle is position 4, which is even. Its value 7 differs from the next value, 9. The alignment already broke, so the single is here or to the left.
Test the middle's pair
Make the middle an even position, since that is where a pair should start if all is well. Now compare it with the next value. If they are equal, the pair is aligned, so the single value is further right, past this pair. If they differ, the alignment has already broken, so the single value is here or to the left.
pair_ok = nums[mid] == nums[mid + 1]
At an even middle position, the value equals the next value. Where is the single one?
- ATo the right of this pair
- BTo the left of this pair
- CAt the middle
Show the answer
To the right of this pair. The pair is aligned, so the single value hasn't occurred yet.
The odd one out
nums is a sorted list of whole numbers (smallest to largest) in which every value appears exactly twice, except for one value that appears once. Return that value.
nums = [1, 1, 2, 3, 3, 4, 4, 8, 8] → 2
1 ≤ length ≤ 100,001 (always odd) · 0 ≤ value ≤ 1,000,000,000