The first solution is quite intuitive and direct but it's not the answer since it will cost another extra O(n) space which is not allowed by the problem. But it's quite simple and easy-understanding, so here it is.

```
//AC - 8ms - using linear space;
int findDuplicate(int* nums, int size)
{
int* arr = (int*)malloc(sizeof(int)*size);
memset(arr, 0, sizeof(int)*size);
for(int i = 0; i < size; i++)
{
arr[nums[i]]++;
if(arr[nums[i]] > 1)
return nums[i];
}
return 0;
}
```

The second solution is to use binary search to search the duplicate considering pigeon hole rule which is quite direct in this case. [1, n] inclusive in the array whose index ranges from [0, n] inclusive, so counting the number less than or equal to the middle can accelerate the searching process.

```
//nlogn time cost and constant space cost;
int findDuplicate(int* nums, int size)
{
int l=1, h=size-1;
while(l < h)
{
int m = (l+h)/2;
int count = 0;
for(int i = 0; i < size; i++)
if(nums[i]>=l && nums[i]<=m) count++;
if(count <= m-l+1) l = m+1;
else h = m;
}
return l;
}
```

The last solution is quite awesome adopting the feature of the linked list in this condition. Reading the comments can be enough to understand the whole thread.

```
//AC - 4ms - using constant space and linear time;
//similar to find the start of the loop in a linked list;
//the integer is the pointer while the index is the link;
int findDuplicate(int* nums, int size)
{
if(size > 0)
{
int slow = nums[0];
int fast = nums[nums[0]];
while(slow != fast) //check the existence of the loop;
{
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(slow != fast) //find the start of the loop which means at least two integer are the same value;
{
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
return -1;
}
```