# Easy (nLogn) Java solution using Sorting and Binary Search.

1. Idea is to sort the array first which itself is NLogN.
2. 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;
}``````

• This solution ignores the firs requirement:

You must not modify the array (assume the array is read only).

• i missed that :(

• assume the array is read only

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.