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


  • 1
    P
    • 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)

    See code:
    https://github.com/zyzyis/OneSizeDoesFitAll/blob/master/src/FindTheDuplicateNumber.c


  • 0
    A

    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!


  • 0
    T

    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!

  • 0
    T

    Good work.

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


  • 0
    G

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


Log in to reply
 

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