This is in fact similar to CodeInChaos's solution: the original question states

You're passed an array with n integers in it.

without saying unsigned integers, so we can toggle the numbers to be negative:

for each elements in array, say if it contains `8`

, then go to element 8 and toggle the number to be negative. If it was already negative, that means it was toggled previously and therefore a duplicate is found.

otherwise, just go on, and if an element we reach has a negative number in it, just take the absolute number (`-10`

becomes `10`

and go to element `10`

to do the toggling)

If it can toggle every element without finding a value inside the array that we want to toggle but is already toggled, then we know there is no duplicate.

at the end, we just go through the array and toggle the elements back to positive numbers. (and O(n + n) is the same as O(n))

we can always negate the number, because such as for an 8-bit integer, the max is `127`

, and the min is `-128`

, so 127 can always be toggled to be -127.

It is a bit like "using an extra bit", but make use of the fact that we can turn the number into a negative one.

if the given numbers are unsigned integers, we can still do it like this:

```
8 7 2 3 5 1 9 6 4
```

we use 2 pointers, one pointing at 8, one pointing at 1, can swap the numbers if the left one is greater than the median, and the right side is less than the median. If the number on either side is "already on the correct side", then just move the pointer one step forward and repeat the above. This will move all numbers to the left and right of the median in the correct group and is O(n).

```
1 4 2 3 5 8 9 6 7
```

now we have this array, we can do the toggling like the above by using `10 - n`

... so if we want to toggle `1`

, we put a `9`

in it, if we want to toggle `6`

, we put a `3`

in it. The idea is, we make it so that it is not supposed to be on the left side, or not supposed to be on the right side, to use as a flag.

So for example, the number `1`

, if it is "toggled", it will be `9`

. The number `9`

is not supposed to be on the left side of the array, so we know that this number has be toggled. It uses the same method as the algorithm first described in this post, only the initial toggling is done by making it a negative number, but this toggling is done by using `(n+1) - i`

This method involves moving the elements, so don't know if it counts as "destroying the array". (or we can use my other method in this thread that involves rearranging the items in array as well)