The following code is done in max O(n) time and without any extra space.

It uses a simple idea based on the constraint given that for an array with n+1 elements, each element can have a value between 1 to n. So we can store the occurrence of a number in that array itself.

Consider the example,

If you find 1 in somewhere in the array. You can simply make the value of a[1] negative. This will give you a count that you have seen a "1" in the array. Now whenever you get "1" again in the array and when you try to check a[1] ..... it will already be negative confirming that it is the element which is the duplicate

Sometime you will come at element which is already made negative by someone before(meaning that its index is the number which is already observed). Hence you have to take abs to handle that.

```
int findDuplicate(vector<int>& nums) {
for(int i=0;i<nums.size();i++){
if(nums[abs(nums[i])] < 0)
return abs(nums[i]);
nums[abs(nums[i])]*= -1;
}
return 0;
}
```