Is it possible to solve this problem fast?

Revision en1, by Theo830, 2020-12-13 14:11:11

Problem: You have some sets and you want to check if set $$$B$$$ is subset of set $$$A$$$. You can erase or insert any element from any set. Let's say that $$$Q$$$ is the number of queries (check,insert or erase) and $$$Q <= 10^5$$$.

I think that may exist a solution using hash function. If you find the binary representation of all the sets (a bit is true only if it exists in the set) if there is a way to find the bitwise AND operation of two hash numbers then if $$$A$$$ & $$$B$$$ $$$=$$$ $$$B$$$ then $$$B$$$ is subset of $$$A$$$.

Any ideas about a solution?

Tags hashing, subset

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Theo830 2020-12-13 14:11:11 573 Initial revision (published)