0

Problem: You are given an array of n+1 integers from range 1..n. At least one number has duplicate. All array values can be same. Print all duplicates in linear time and constant space. Array can't be modified.

The obvious solution would be to create a bit array with default value false, set 1 in bitarray[array[i]] for each element, then check if it's already 1. That requires additional space, so no good. My another thought: reorder the array by hash and check if a current element and the element array[hash % n] are equal. This is also no good since we can't modify the original array. Now I think that it looks like an impossible task. Is there even a solution to this?

Anguium
  • 41
  • 2
  • 4
  • 1
    This may be a duplicate of https://stackoverflow.com/questions/5766936/find-the-missing-and-duplicate-elements-in-an-array-in-linear-time-and-constant. Even if it isn't that Q, and others here on SO, provide much to consider. – High Performance Mark Nov 12 '18 at 17:35
  • Not sure if this makes sense, but I'm thinking one possible algorithm would be to have some mapping for each number in `1..n` to another number such that all the mappings are coprime to each other. If you can get that, then you could just have start with `m = 1` and, for each element, if `m % mapped_elem == 0` then it is duplicate, otherwise do `m *= mapped_elem`. However I don't know if it's possible to do such mapping (quickly). – jdehesa Nov 12 '18 at 18:17
  • 4
    Is this even possible in the general case? Imagine `n=999999` and the array contains the numbers 1 through 1000, duplicated 1000 times each. If I can't modify the array or use additional space proportional to n, it doesn't seem likely that this can be done in linear time. Are you sure there are no other restrictions on the input? – Jim Mischel Nov 12 '18 at 18:29

0 Answers0