- Idea is to sort the array first which itself is NLogN.
- Now there is a small modification in binary search. If mid element is >= (mid + 1) then there is number which is skipped from left part of the array and Hence duplicate lies on the other part.

Total complexity is (NlogN + LogN) = O(NLogN)

Note : I took hint from TAGS mentioned in the question iteself. Any improvement or modification would be appreciated. :D

```
public int findDuplicate(int[] nums) {
Arrays.sort(nums);
int lo = 0 ;
int high = nums.length - 1 ;
int mid = -1;
while(lo < high){
mid = lo + (high - lo)/2 ;
if(mid > 0 && nums[mid] == nums[mid -1]){ // if mid element is duplicate
return nums[mid];
}else if(mid + 1 < nums.length && nums[mid] == nums[mid + 1]){ // if mid element is duplicate.
return nums[mid];
}else if(nums[mid] >= mid + 1){ // change lo and high according to mid value
lo = mid + 1;
}else{
high = mid - 1;
}
}
return 0;
}
```