Single element in sorted array
MicrosoftThe problem
Given an array nums sorted in non-decreasing order. Every number in the array except one appears twice. Find the single number in the array.
Input :nums = [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6] Output:4 Explanation: Only the number 4 appears once in the array.
Input : nums = [1, 1, 3, 5, 5] Output:3 Explanation: Only the number 3 appears once in the array.
Input :nums = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7]
- n == nums.length
- 1 <= n <= 104
- -104 <= nums[i] <= 104
cpp
class Solution {
public:
int singleNonDuplicate(vector<int> &nums) {
}
};java
class Solution {
public int singleNonDuplicate(int[] nums) {
}
}python
class Solution:
def singleNonDuplicate(self, nums):javascript
class Solution {
singleNonDuplicate(nums) {
}
}csharp
public class Solution {
public int SingleNonDuplicate(int[] nums) {
}
}go
func singleNonDuplicate(nums []int) int {
}Stuck? Show a way to structure it+
- 01Keep a search interval over indices.
- 02Normalize middle to an even pair-start index.
- 03Compare that index with its partner.
- 04Move right when the pair is intact.
- 05Otherwise keep the left half including middle.
Reference answer
Then expect these follow-ups
How would you solve it if every other value appeared three times?
Tests: complexity analysis
Can you prove the parity shift formally?
Tests: correctness reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question