class Solution {

public:

int findDuplicate(vector<int>& nums) {

```
if(!nums.size())
return -1;
// Here we will use a marking strategy to identify the duplicate
// Specifically we will mark the number at the array position of
// a visited item as -ve (e.g we will mark nums[2] as -nums[2]
// when we encounter a 2 while iterating over the array elements)
// Then if we ever encounter the same number again and the value
// at that position (say 2 as in the above example) in the array is -ve - we know its a duiplicate.
// This is guaranteed by the fact that all numbers are between 1 and n (i.e nothing is -ve in the begining)
// and that there is only 1 duplicate (which is why we can bail out as soon as we find one and not have to save anything
// there by meeting the requirements in the question.
for(int i=0;i<nums.size();++i)
{
// Computing the absolute value once reduce runtime from >20ms to 12ms
int absoluteValueAtNumsIthPosition = std::abs(nums[i]);
if(nums[absoluteValueAtNumsIthPosition ] > 0)
nums[absoluteValueAtNumsIthPosition ] = -nums[absoluteValueAtNumsIthPosition ];
else
return absoluteValueAtNumsIthPosition ;
}
}
```

};