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:
1 <= nums.length <= 1050 <= nums[i] <= 105This approach leverages the sorted property of the array to perform a binary search, achieving a time complexity of O(log n). The key observation is that elements are paired, except for the single unique element. Thus, we can use the middle index to determine if the unique element is in the left or right half of the array based on the pairing pattern.
The binary search here divides the array into two halves. If the middle element is equal to the element next to it and its index is even, it implies the single element is in the second half. Otherwise, it's in the first half. This process continues until left equals right, pointing to the single element.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n)
Space Complexity: O(1)
This approach exploits the properties of the XOR operation: a ^ a = 0 and a ^ 0 = a. We can XOR all elements, and since duplicates XOR to 0, only the unique element will remain.
The XOR operation cancels out all duplicates, leaving only the single unique element. This takes advantage of the property that x ^ x = 0 and x ^ 0 = x.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Binary Search | Time Complexity: O(log n) |
| Bitwise XOR | Time Complexity: O(n) |
BS-8. Single Element in Sorted Array • take U forward • 225,633 views views
Watch 9 more video solutions →Practice Single Element in a Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor