Problem statement: Give two sets A and B, devise and algorithm that checks if A and B are disjoint. The following information are given about the set A and B:
Ask questions if you need to or send me a Private message
No body is curious enough I guess. Can anyone suggest an algorithm that runs in polynomial time first? Then maybe go on to linear timing.
Well I'm certainly curious to see if a linear time algorithm exists, can't think of any.
As a starter, I can think of a few basic methods:
- Brute force: pick each element of A and do a linear search for its match in B. If a match is found, then the sets are not disjoint. If the complete search doesn't yield a match, the sets are disjoint. That would be essentially O(n^2) in time.
- Sort and search: sort both arrays, in O(nlog(n)) time, and then progress through both A and B at the same time to look for matches, in O(n) time. Overall that would be O(nlog(n)) still.
- Joint and sort: treat both sets as one big set and sort the set while looking for duplicates (assuming there are no duplicates in the original sets A and B). That would still be O(nlog(n)).
Any other suggestions?
It definitely can be done in linear time, just because of its special nature, that is because of the properties, 1,2,3,4 listed above.
It definitely can be done in linear time, just because of its special nature, that is because of the properties, 1,2,3,4 listed above.
Indeed. I had figured that the reason that no one bothered to answer it was that it was so easy.
However, since no one has made any progress so far, I'll give a few hints:
1) The O(n) space requirement means that it is possible to make temporary copies of the arrays. Therefore, we can assume without loss of generality that it is OK for the algorithm to change the contents of the arrays.
2) The constraints on the values of the array elements means that it is possible to use a radix sort to sort them, which is O(n).
3) Once the arrays are sorted, there is a trivial O(n) algorithm to determine whether they are disjoint.
I'll leave the code to someone else.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.