# 4ms C program, Space O(1), Time O(N)

• find a big non-exist prime number ( magic number )

• go through the list, if the number is dividable by the magic number, it is the solution.

• other wise, multiply the number by the magic number

• scan again, un touch the array.

• Space complexity O(1)

• Time Complexity O(N)

• Your code does not fully untouch the array. There must be a hole in the test case. Consider the array:

``````[1, 8, 3 ,4, 2, 3, 7, 6, 5]
``````

The final array at the end of your code looks like:

``````[1, 8, 3 ,4, 2, 3, 7, 6, 5*secret]
``````

Otherwise, very nice solution!

• His idea is very tricky! Actually, we could understand as follows:

1. allocate an extra bool vector, bool exist[N].
2. For d in data:
if exist[d]: return d
otherwise exist[d] = true;

But he does not allocate extra memory, and uses a special mark, magic number, termed M.
then if (d * M % M == 0), we know d was marked before.

I have some concerns.

1. First, how to define such a magic number?
2. This would lead to a potential overflow.
3. This problem requires not to modify the input data. In C++, there is a constant keyword. But his method is really tricky and interesting,
as after running the function, the input data could be restored!

• Good work.

I have some concerns following the first reply to your post. Thanks.

• You must not modify the array (assume the array is read only).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.