**Note:** This is an AC solution, but not correct. I violated the "treat the list as read-only". Otherwise it's correct.

Algorithm: Just go through the array, treat every absolute value as an index. Just flip the nums[index] to negative.

If the nums[index] is already negative, then it means it has already been flipped. Then "index" is the duplicated number.

e.g.

5 2 1 3 4 5 6

We go through the numbers: (x) is the current one, [y] is the flipped one

(5) 2 1 3 4 [-5] 6

5 (2) [-1] 3 4 -5 6

5 [-2 ] (-1) 3 4 -5 6

5 -2 -1 [(-3)] 4 -5 6

5 -2 -1 -3 [(-4)] -5 6

5 -2 -1 -3 -4 [(5)] 6 <--- Now the 5 is positive, means it has already been flipped, the index is duplicated

# Python Code

```
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
index = abs(nums[i])
nums[index] *= -1
if nums[index] > 0: return index
```

# C++ Code

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