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:
Example 2:
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
For Example
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
For Example
We can apply binary search to validate the elements at the mid index.
if
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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)); } } |
Output
Complexity Analysis
Time complexity: O(logN).Space Complexity: O(1).
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.