This problem is quite easy if there are not so many requirements.

And the **reqirement** ** "Array must not be modified"** costs me much time to think out

the following solution eventually much time.

Any more faster solutions ? If yes, pls tell me, thx very very much.

```
int _duplicated (const int *nums, int numsSize, int start, int end)
{
int n, i, m, mc;
if (start == end) return start;
m = (start + end) >> 1;
for (i = n = mc = 0; i < numsSize; ++i) {
if (nums[i] == m) {
++mc;
} else if (nums[i] > m && nums[i] <= end) {
++n;
}
}
if (mc > 1) return m;
if (n > end - m) return _duplicated (nums, numsSize, m + 1, end);
else return _duplicated (nums, numsSize, start, m - 1);
}
int findDuplicate(int* nums, int numsSize)
{
return _duplicated (nums, numsSize, 1, numsSize - 1);
}
```