CODEWITHSUNDEEP
algorithmhash
Media Splitz
Media Splitz

Reputation: 1

Algorithm to determine if 2 arrays are disjoint

Give a randomized expected linear-time algorithm using ideal hash functions that determines whether two arrays A[1..n] and B[1..n] are disjoint, i.e., whether no element of A is also an element of B.

Can anyone show me how to do this or even how to start thinking about it?

Upvotes: 0

Views: 237

Answers (1)

Ole Tange
Ole Tange

Reputation: 33740

for element in a:
  hasha{element} = 1

for element in b:
  if hasha{element} == 1:
    print element "found in both"

Time: O(len(a)+len(b))

Upvotes: 3

Related Questions