LeetCode - 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. Find this single element that appears only once.

Example 1:

Input: [1,1,2,3,3,4,4,8,8] Output: 2

Example 2:

Input: [3,3,7,7,10,11,11] Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

Solution

There are many approaches to the solution,

1. We can do XOR of all elements, result of that will be the unique number from the Array.

2. As array is sorted we can iterate through it and find unique element.

Above approaches having time complexity as O(N), We would like to get the result in log(N) complexity.

3. First let’s understand with no unique element present in the Array, only duplicate elements are present, in that case as our Array is sorted so all similar element will have index as m and m+1

For Example

int [] = {2,2,3,3,4,4,5,5,6,6} index 0,1,2,3,4,5,6,7,8,9

Now let’s say we have unique number present in the Array, index where this element is present from that onwards similar element is no more present at m and m+1 with respect to the 0index.

For Example

int [] = {2,2,3,3,4,5,5,6,6,7,7} index 0,1,2,3,4,5,6,7,8,9,10

We can apply binary search to validate the elements at the mid index. if m and m+1 having same elements then unique elements lies on right side, else on left side.

Code


public class SingleElement {

	public int singleNonDuplicate(int[] nums) {

		int n = nums.length, lo = 0, hi = n / 2;
		while (lo < hi) {
			int m = (lo + hi) / 2;
			if (nums[2 * m] != nums[2 * m + 1])
				hi = m;
			else
				lo = m + 1;
		}
		return nums[2 * lo];
	}

	public static void main(String[] args) {

		int[] a = { 1, 1, 2, 3, 3, 4, 4, 8, 8 };
		SingleElement sn = new SingleElement();
		System.out.println(sn.singleNonDuplicate(a));

	}
}