Problem statement
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.
Example 1
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2
Input: nums = [3,3,7,7,10,11,11]
Output: 10
Constraints
Solution 1: Bruteforce
Code
#include <vector>
#include <iostream>
using namespace std;
int singleNonDuplicate(vector<int>& nums) {
for (int i = 0; i < nums.size() - 1; i += 2) {
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return nums[0];
}
int main() {
vector<int> nums{1,1,2,3,3,4,4,8,8};
cout << singleNonDuplicate(nums) << endl;
nums = {3,3,7,7,10,11,11};
cout << singleNonDuplicate(nums) << endl;
nums = {3};
cout << singleNonDuplicate(nums) << endl;
}
Output:
2
10
3
Complexity
Solution 2: Binary search
Since nums is sorted, you can perform a binary search on it.
Let us divide nums into two halves.
If the single element belongs to the right half, all elements of the left half satisfy nums[2*i] == nums[2*i + 1].
Conversely, if the single element belongs to the left half, that condition is violated at the middle element of nums (the middle one with an even index).
Example 1
For nums = [1,1,2,3,3,4,4,8,8]:
The middle element with even index is nums[4] = 3. It is not equal to nums[4 + 1] = 4. So the single element must be somewhere in the left half [1,1,2,3,3].
The middle element of nums = [1,1,2,3,3] with even index is nums[2] = 2, which is not equal to nums[2 + 1] = 3. So the single element must be somewhere in the left half [1,1,2].
The middle element of nums = [1,1,2] with even index is nums[0] = 1 == nums[0 + 1]. So the single element must be somewhere in the right half [2].
nums = [2] contains only one element. So 2 is the result.
Code
#include <vector>
#include <iostream>
using namespace std;
int singleNonDuplicate(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = (right + left)/4 * 2;
if (nums[mid] != nums[mid + 1]) {
right = mid;
} else {
left = mid + 2;
}
}
return nums[right];
}
int main() {
vector<int> nums{1,1,2,3,3,4,4,8,8};
cout << singleNonDuplicate(nums) << endl;
nums = {3,3,7,7,10,11,11};
cout << singleNonDuplicate(nums) << endl;
nums = {3};
cout << singleNonDuplicate(nums) << endl;
}
Output:
2
10
3
Complexity
Reference
Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.
