The forum has two solutions1) Loop detection, 2) Binary Search. Throw in another idea, O(N), using bucket sort. Consider the number n belong to bucket num[n-1].

When we put each number in their bucket. If duplicate exists, then we should find nums[nums[i]-1]==nums[i], otherwise, we should be able to traverse the array in O(N) time.

```
public class Solution {
public int findDuplicate(int[] nums) {
for(int i=0;i<nums.length;i++){
while(nums[i]!=i+1){
int j = nums[i]-1;
if(nums[i] == nums[j]) return nums[i];
else swap(nums, i, j);
}
}
//not found
return 0;
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```