1+ /*
2+ * Time complexity: O(n)
3+ * Space complexity: O(1)
4+ */
5+
6+ class Solution {
7+ public int singleNonDuplicate (int []nums ) {
8+ int n =nums .length ;
9+ int left =0 ,right =n -1 ;
10+
11+ // if nums only has one element
12+ if (n <2 )return nums [0 ];
13+
14+ // if the answer lies at either end of the array
15+ if (nums [left +1 ] !=nums [left ])return nums [left ];
16+ if (nums [right -1 ] !=nums [right ])return nums [right ];
17+
18+ // when you see requirement of O(log n) time and O(1) space
19+ // most of the time you gonna need binary search
20+ // either that or some hacky method using math or bitwise
21+ while (left <right ) {
22+ int mid =left + (right -left )/2 ;
23+ int curr =nums [mid ];
24+ // we already check either end so mid will never gonna be out of array's bound
25+ int prev =nums [mid -1 ];
26+ int next =nums [mid +1 ];
27+
28+ // if mid lands on the result, just return it
29+ if (prev !=curr &&curr !=next )return curr ;
30+
31+ // because there are no others criteria
32+ // remember to check the array's index to see if you miss anything
33+ // you can see that the even index should always be the start of the duplication
34+ // so if the sequence is broken: left of odd index is still a duplicate, the sequence
35+ // was broken before that index -> right = mid and vice versa
36+ if (mid %2 ==0 ) {
37+ if (curr !=prev )left =mid +1 ;
38+ else right =mid ;
39+ continue ;
40+ }
41+
42+ if (curr ==prev )left =mid +1 ;
43+ else right =mid ;
44+ }
45+ return nums [left ];
46+ }
47+ }