Given two arrays of integers, A and B, with same size (or two bit vectors A and B with some bits enabled)

What would be the faster way to create a list C containing the elements from B not in A, (or the indexes of the bit vector B not enabled in A)?


The two questions are rather different. If $A$ and $B$ are given as unsorted lists, then one thing you could do is to sort $A$ and $B$ together, putting elements of $A$ before those of $B$ in case of ties, and then do a simple linear scan. This runs in $O(n\log n)$ time, where $n$ is the length of both arrays.

If the arrays are sorted then you can just merge them, in $O(n)$, and continue as before.

If the "arrays" (really sets) are given as bit-vectors, then you can use bitwise operations; details left to you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.