# O(n) time & O(1) space easy to understand Java solution

• The main idea is comparing nums[0] with the element in its destination nums[nums[0]]. If the position is taken, then nums[0] is the duplicate element. Otherwise, swap it to the destination, and continue on the previous process. The duplicate element can be detected with at most m steps.

``````class Solution {
public int findDuplicate(int[] nums) {
int m = nums.length;
for(int i = 0; i < m; ++i) {
int temp = nums[nums[0]];
if(nums[0] == temp) {
return nums[0];
} else {
nums[nums[0]] = nums[0];
nums[0] = temp;
}
}
return -1;
}
}
``````

Binary Search Solution with the idea from https://discuss.leetcode.com/topic/27420/java-o-1-space-using-binary-search.

``````class Solution {
public int findDuplicate(int[] nums) {
int start = 1, end = nums.length - 1;
while(start < end) {
int mid = start + ((end - start) >> 1);
int count = 0;
for(int n : nums) {
if(n <= mid) {
++count;
}
}
if(count <= mid) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
}
``````

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