Interview task: check if array consists of pairs in O(n) time and O(1) of additional memory

Question

Here is one example of task that I was asked on the interview which I believe was either misspelled or improperly defined but maybe I'm wrong, so here goes:

It is required to provide an implementation of function which checks that the argument array consists of duplicates only, as an example there were two arrays provided:

var x = [11,12,11,12]; // True, array consists of duplicates
var y = [66, 3278, 12, 12]; // False, 66 and 3278 contain no pair

The problem is in constraints the algorithm should perform this check in O(n) time, with O(1) memory space

What do you think, is it possible, because I don't see a way that can happen...

Answer 1

Impossibility results are much harder to come by than algorithms, so it's frustrating to have an apparently unsolvable problem like this.

Certainly there's no one-pass algorithm, by a communication complexity argument over the midpoint of the input. With (e.g.) only k words of storage, remembering the precise multiset from the first k+1 items is impossible, so we can follow those items with another k+1 that cause an incorrect output.

On the flip side, there's a probabilistic algorithm that succeeds most of the time. Compute the XOR of a pseudorandom function applied to each input element, and return that the elements are paired if and only if the XOR is 0. As Peter observes in the comments, it is insufficient to let the pseudorandom function be the identity, due to inputs like {0, 1, 2, 3}. The point of the PRF is to bring the properties of linear algebra over Z/2 to bear such that the probability of getting a spurious zero is equal to the probability that a random word is zero, which, for a long word, is quite small.

Answer 2

• Start with 1.
• For every number x, from the array, multiply by the x'th prime number.
• If the result is a square number, the array only contained duplicates. (or maybe a few quadruples, or other multipele twins)