The one value without a partner
A sorted array contains every value exactly twice, except one value that appears once. Return that value in O(log n) time and O(1) extra space.
Examples
| Input | Output | Why |
|---|---|---|
a = [1, 1, 2, 3, 3, 4, 4, 8, 8] | 2 | |
a = [3, 3, 7, 7, 10, 11, 11] | 10 | |
a = [5] | 5 |
Constraints
- 1 ≤ n ≤ 10⁵, n odd
- −10⁵ ≤ a[i] ≤ 10⁵
- a is sorted
Hints
Hint 1
XOR of everything finds the value in O(n). What does sortedness add?
Hint 2
Look at the indices of each pair before the single value, and after it. Which index does each pair start on?
Hint 3
Before the single value, a pair starts at an even index i with a[i] = a[i + 1]. From the single value on, that fails. Search for the first even index where a[i] ≠ a[i + 1].
Where people lose marks
- Testing odd values of mid against mid + 1, which compares the second element of one pair with the first of the next.
- Reading a[mid + 1] when mid = n − 1. With hi = n − 1 and mid made even and below hi, it never happens.
- Returning the index rather than the value.
Dry run on [2,2,5,5,6,6,9,11,11,14,14,20,20]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5lo0hi12
Test at even indices only: does a[i] differ from a[i + 1]? It fails before the single value and passes from it onwards.
-
Step 2 / 5lo0mid6hi12
a[6] = 9 and a[7] = 11: they differ, so the single value is at 6 or before: hi = 6.
-
Step 3 / 5lo0mid2hi6
The middle, 3, is odd; step back to 2. a[2] = 5 and a[3] = 5: a pair starting at an even index, so everything up to 3 is paired normally: lo = 4.
-
Step 4 / 5lo4mid4hi6
The middle, 5, is odd; step back to 4. a[4] = 6 and a[5] = 6: a pair starting at an even index, so everything up to 5 is paired normally: lo = 6.
-
Step 5 / 5answer9
lo = hi = 6: the value without a partner is 9.
How to think about it
XOR-ing every element gives the answer in O(n) and ignores the fact that the array is sorted. The sorted order puts each pair side by side, and the single value shifts every pair after it by one place.
- Before the single value, pairs occupy indices (0, 1), (2, 3), …: at every even index
i,a[i] = a[i + 1]. - At the single value's index, which is even, and at every even index after it, the pair has been pushed to
(odd, even), so
a[i] ≠ a[i + 1].
So the test "a[i] ≠ a[i + 1]", read only at even indices, is false then true, and the single value
sits at the first even index where it is true. Binary search over the even indices: make mid even
(subtract 1 if it is odd), then keep the left part if the test passes and the right part if it fails.
The test does not depend on the values at all, only on whether neighbours match. That is the sign of a structural search: the array is sorted, but the property being searched is position parity.
Complexity. Time O(log n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def single_value(a):
lo, hi = 0, len(a) - 1 # the single value's index is in [lo, hi]; both even
while lo < hi:
mid = (lo + hi) // 2
if mid % 2 == 1:
mid -= 1 # test only even indices: mid < hi stays true
if a[mid] != a[mid + 1]:
hi = mid # the pairing is already broken here
else:
lo = mid + 2 # a[mid], a[mid + 1] is a normal pair
return a[lo]#include <vector>
int solve(const std::vector<int>& a) {
int lo = 0, hi = (int)a.size() - 1; // both even; the answer's index is in [lo, hi]
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) --mid; // test only even indices
if (a[mid] != a[mid + 1]) hi = mid;
else lo = mid + 2;
}
return a[lo];
}class Solution {
public int singleValue(int[] a) {
int lo = 0, hi = a.length - 1; // both even; the answer's index is in [lo, hi]
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid--; // test only even indices
if (a[mid] != a[mid + 1]) hi = mid;
else lo = mid + 2;
}
return a[lo];
}
}function singleValue(a) {
let lo = 0, hi = a.length - 1; // both even; the answer's index is in [lo, hi]
while (lo < hi) {
let mid = (lo + hi) >> 1;
if (mid % 2 === 1) mid--; // test only even indices
if (a[mid] !== a[mid + 1]) hi = mid; // pairing broken at or before mid
else lo = mid + 2; // a normal pair
}
return a[lo];
}fn solve(a: &[i64]) -> i64 {
let (mut lo, mut hi) = (0usize, a.len() - 1); // both even
while lo < hi {
let mut mid = lo + (hi - lo) / 2;
if mid % 2 == 1 {
mid -= 1; // test only even indices
}
if a[mid] != a[mid + 1] { hi = mid } else { lo = mid + 2 }
}
a[lo]
}import Data.Array
solve :: [Int] -> Int
solve xs = a ! go 0 (n - 1)
where
n = length xs
a = listArray (0, n - 1) xs
-- lo and hi stay even; test only even indices
go lo hi
| lo >= hi = lo
| a ! m /= a ! (m + 1) = go lo m
| otherwise = go (m + 2) hi
where
mid = lo + (hi - lo) `div` 2
m = if odd mid then mid - 1 else midVariants to try
- Unsorted input: XOR every element, O(n) and O(1) space.
- Every value appears three times except one: count each bit modulo 3.
- Two values appear once: XOR all, split by any set bit of the result, XOR each group.
Next problems
The top of a mountain array
Nothing is sorted, but "is the next element smaller?" is false up the slope and true down it. Find the first true.
Open the problem → Hard25 minFind a value in a mountain array
Find the peak, then search the rising side in ascending order and the falling side in descending order. Left side first, for the smallest index.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
The top of a mountain array
Nothing is sorted, but "is the next element smaller?" is false up the slope and true down it. Find the first true.
Open the problem → Hard25 minFind a value in a mountain array
Find the peak, then search the rising side in ascending order and the falling side in descending order. Left side first, for the smallest index.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.