### acc1's blog

By acc1, 11 years ago,
Given Two arrays of n numbers. Find Whether they are disjoint or not.

Each Element lie in range [0,n^100] .

Space : O(n)

• +1

 11 years ago, # |   0 If you mean expected O(n) then this is just a hash-table problem.
 11 years ago, # |   0 You can unify these arrays to one and sort it by radix sort. Then you can find two adjanced equal items in large array, which were in different arrays. If you can find this, arrays aren't disjoint.Sorry for bad English...
•  11 years ago, # ^ | ← Rev. 2 →   +3 Ooops I missed to mention, O(n) memory is only there .. :P
•  11 years ago, # ^ |   +5 And this algo uses only O(n) memory because radix-sort is O(n) memory and O(k*n) time (but k is const) and check-up is O(1) memory and O(n) time.
•  11 years ago, # ^ |   0 I think that input file holds more memory than program can use.
 11 years ago, # |   +3 Hash - Table ..mmm..but it is implemented using rb tree, then how come O(n) ? , then it will get O(n*lgn) ....Answer above question, and one more thing , can we do this using bitwise kung-fu , like Xoring (just a guess) .
•  11 years ago, # ^ |   0 No, hash tables works in O(n). Try to read this.
•  11 years ago, # ^ |   +3 Okay, Thanks.Seems Correct.So, Is there any other way ?
•  11 years ago, # ^ |   0 Hash table do not use rb tree. Never
 11 years ago, # |   0 How about using a set? Store all the numbers of the first array in a set. A set only requires O(log(n)) time for instertion and search. And it also requires O(n) memory AFAIK.
•  11 years ago, # ^ |   0 Are you read previous comments?
 11 years ago, # |   +3 Size of input in this problem is O(n * log(n100)) = O(nlog(n)) so it can't be solved in O(n) time. At least unless we have some special agreements about working with long numbers in O(1) time.
•  11 years ago, # ^ |   0 Yes, You are given with that liberty.Here input size can be taken as O(n) .Although it should be n*log(n) when considered, in bits.But Here Assume log(n) is ignored and..we are working with long numbers in O(1).