# O(n)solution in 1 loop, no extra space

• The idea is, cuz we know the value of each element is bounded, and the range is 1~n, which is just the range of index 1~n of the input array, then each time when we met a new element nums[i], we can just throw it to the "place it should be", which has the index = nums[i].
In the meantime we don't wanna lose track of each original element at index nums[i], so we just make a mark at that place!
Simply let nums[index] = -nums[index], where index = nums[i].
Math.abs(nums[i]) is the original element nums[i] that is not marked yet.
Then every time, if we find that nums[index] is already marked, we must encounter a duplicate nums[i], which leading us to the same place that we've marked before.

``````public int findDuplicate(int[] nums) {
for(int i = 0;i<nums.length;i++){
int index = Math.abs(nums[i]);
//in case we find the dupicate
if(nums[index]<0) return index;
nums[index]=-nums[index];
}
//If we don't find it then return default value, could be anything.
return 0;
}``````

• @tongzhou2 You have modified the array. The NOTE is "You must not modify the array (assume the array is read only)."

• @zhongtaovip Yes you're right I didn't notice that before.

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