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
Hiring now
Get the Microsoft interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question