Are two arrays permutation of each other? [duplicate]

Question

Possible Duplicate:
Check if array B is a permutation of A

Given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space?

The first solution that came to my mind is that is using XOR, i.e. XOR all the elements of a and b and if the resultant is 0 which means that b is a permutation of a. But he gives examples where this approach fails. For e.g -

a: [1 6 0 0 4] -- b: [1 0 6 1 5]
a: [1 6 0 0 5] -- b: [1 0 6 1 4]

Any one having any idea, that how to do it in O(n) time and O(1) space?

Answer 1

In the case of a bounded range of integers - let that range be [n,m] such that m-n = U you can sort the arrays using in place radix sort, also discussed in this great post.

After you have two sorted arrays - a simple iteration on both can give you the answer - the original arrays are permutations of each other if and only if the sorted arrays are identical.

Note:
There is some "cheating" in this answer [thus I did not post it until the OP asked for it in comments..], since the time complexity of it is O(nlogU), and space is O(logU). However, for bounded ranges - we can assume O(logU) = O(1), and for these cases we get O(n) time and O(1) space.

Answer 2

If your set elements are non-negative, and you have an unbounded integer type (a BigInteger or similar) available, you could define a function over a set A:

C(A) = product(p_(a+1))) for each a in A

where p_nis the nth prime number. Then C depends only on the values in A, rather than their order; and any change to the values changes C.

For example,

C([1 6 0 0 4]) = p_2.p_7.p_1.p_1.p_5 = 3.17.2.2.11 = 2244

(and obviously any set with the same elements has the same C, whatever the order), and

C([1 6 0 1 4]) = p_2.p_7.p_1.p_2.p_5 = 3.17.2.3.11 = 3366

so we know these sets are different. This uses the fundamental theorem of arithmetic which states that any integer greater than 1 can be written as a unique product (up to ordering of the factors) of prime numbers. Or maybe it uses a corollary. I just made this method up, so it might not work. This post is not an attempt at a proof of its correctness...