Find unique common element from 3 arrays

Question

Original Problem:
I have 3 boxes each containing 200 coins, given that there is only one person who has made calls from all of the three boxes and thus there is one coin in each box which has same fingerprints and rest of all coins have different fingerprints. You have to find the coin which contains same fingerprint from all of the 3 boxes. So that we can find the fingerprint of the person who has made call from all of the 3 boxes.

Converted problem:
You have 3 arrays containing 200 integers each. Given that there is one and only one common element in these 3 arrays. Find the common element.
Please consider solving this for other than trivial O(1) space and O(n^3) time.

Answer 1

Some improvement in Pelkonen's answer:
From converted problem in OP:

"Given that there is one and only one common element in these 3 arrays."

We need to sort only 2 arrays and find common element.

Answer 2

If you sort all the arrays first O(n log n) then it will be pretty easy to find the common element in less than O(n^3) time. You can for example use binary search after sorting them.

Answer 3

Let N = 200, k = 3,

1. Create a hash table H with capacity ≥ Nk.

2. For each element X in array 1, set H[X] to 1.

3. For each element Y in array 2, if Y is in H and H[Y] == 1, set H[Y] = 2.

4. For each element Z in array 3, if Z is in H and H[Z] == 2, return Z.

5. throw new InvalidDataGivenByInterviewerException();

O(Nk) time, O(Nk) space complexity.