alex1988 - 1 year ago 67

C Question

There is an array of 1000 elements, all the elements are Normally distributed within a range of 1 - 10000000. How can I check for duplicates faster than

`O(n^2)`

Answer Source

You can do it in `O(max_num + n)`

time complexity and in `O(max_num)`

space complexity, where `max_num`

is maximum number you can have in your array, using additional array.

You allocate new array `countsArr`

of size 10000001 and initialize all of it's elements to `0`

. Then you iterate over your primary array, and in every iteration, you add `1`

to the new array's element on the index of the number you are currently processing. For example, on first position of your primary array is number `15`

, so you add `1`

to `arr[15]`

, etc. After you are done with the iteration, you just iterate over `countsArr`

, and if you find an element, which value is greater than `1`

, then there are duplicities in your array, otherwise there are not.

EDIT: This is generally faster solution than `O(n^2)`

for large n, but since you have 1000 elements, `1,000^2 = 1,000,000`

, `O(n^2)`

will be actually faster for `n = 1,000`

than the solution I proposed.