Algorithm


Problem Name: 540. Single Element in a Sorted Array

 

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 <= 105
  • 0 <= nums[i] <= 105

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1;
        int mid = (lo + hi) / 2;
        while(lo  <  hi - 2){
            if(nums[mid] == nums[mid + 1]) mid++;
            if((hi - mid) % 2) lo = mid + 1;
            else hi = mid;
            mid = (lo + hi) / 2;
        }
        return nums[lo] == nums[lo + 1] ? nums[hi] : nums[lo];
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,1,2,3,3,4,4,8,8]

Output

x
+
cmd
2

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int singleNonDuplicate(int[] nums) {
    if (nums.length == 1) {
      return nums[0];
    }
    return binarySearchHelper(nums, 0, nums.length - 1);
  }
  
  private int binarySearchHelper(int[] nums, int start, int end) {
    if (start > end) {
      return Integer.MIN_VALUE;
    }
    int mid = (start + end) / 2;
    if (mid == 0 && mid + 1  <  nums.length && nums[mid] != nums[mid + 1]) {
      return nums[mid];
    }
    if (mid == nums.length - 1 && mid - 1 >= 0 && nums[mid] != nums[mid - 1]) {
      return nums[mid];
    }
    if (mid + 1  <  nums.length && nums[mid] != nums[mid + 1] && mid - 1 >= 0 && nums[mid] != nums[mid - 1]) {
      return nums[mid];
    }
    return Math.max(binarySearchHelper(nums, start, mid - 1), binarySearchHelper(nums, mid + 1, end));
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,1,2,3,3,4,4,8,8]

Output

x
+
cmd
2

#3 Code Example with Javascript Programming

Code - Javascript Programming


const singleNonDuplicate = function(nums) {
  let i = 0;
  while (true) {
    if (nums[i] == nums[i + 1]) {
      i += 2;
    } else {
      return nums[i];
    }
  }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [3,3,7,7,10,11,11]

Output

x
+
cmd
10

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums)-1
        while left<=right:
            mid = (left+right)//2
            if mid+1=0 and nums[mid] == nums[mid-1]:
                if mid % 2 == 0: right = mid-2
                else: left = mid+1
            else: return nums[mid]
                
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [3,3,7,7,10,11,11]

Output

x
+
cmd
10

#5 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _0540_SingleElementInASortedArray
    {
        public int SingleNonDuplicate(int[] nums)
        {
            int lo = 0, hi = nums.Length - 1;
            while (lo  <  hi)
            {
                int mid = lo + (hi - lo) / 2;
                if (mid % 2 == 1) mid--;
                if (nums[mid] == nums[mid + 1])
                    lo = mid + 2;
                else
                    hi = mid;
            }

            return nums[lo];
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,1,2,3,3,4,4,8,8]

Output

x
+
cmd
2
Advertisements

Demonstration


Previous
#539 Leetcode Minimum Time Differenc Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#541 Leetcode Reverse String II Solution in C, C++, Java, JavaScript, Python, C# Leetcode