Arrays are permutation of each other

Problem Definition – Arrays are permutation of each other

The problem definition goes as follows: Given two arrays of equal length, find out if the elements of one array is the permutation of the elements of another array.

Of course the constraint is to solve it in constant space and linear time. Which means that the running time should be O(N) and auxiliary space required should be O(1).

Approach

There may be several thoughts which seem to work but eventually they will fail at one or the other ways. Here are few interesting ways which may not work for all the conditions:

  • XORing the elements of both the arrays and the final result should be zero. As we know that the XOR will give a zero if a pair of elements to be tested is equal. This case however fails when the arrays contain duplicate elements and one zero each. For e.g. a=[0,5,5] and b= [8,0,8] will give a zero upon XORing, but they are not permutations of each other.
  • Adding the elements of each arrays individually. If the sums are equal then they are permutations. This fails miserably.
  • Multiplying the elements of each arrays individually. If the products are equal then they are permutations. This fails miserably because there can be various distinct sets of numbers whose products can be equal.
  • Summing the Squares of each element of both arrays individually. If the sums are equal then they are permutations. This is better compared to the Adding solution, but this will also fail at some point.
  • Combining the Addition and Multiplication take sum (sumA and sumB) of elements of both the arrays separately. Then take product (productA and productB) of elements of both the arrays. If sumA equals to sumB and productA equals to productB then the arrays are permutations of each other.

Solution – Arrays are permutation of each other

The correct solution to this problem is as follows:
From all the experiments above, we realized that the last one is more promising. Still there is a flaw because if there is a zero in both the arrays then the product will miserably fail and result in zero and productA will always be equal to productB.

So being extra cautious, we need to account for 0s and 1s and then the last solution works. So, let us count the number of zeroes in each of the arrays and say aZeroes and bZeroes. Now count the number of ones in each of the arrays and say aOnes and bOnes.

Now find productA and productB and sumA and sumB as defined by the above approach.

If aZeroes equals to bZeroes, aOnes equals to bOnes, productA equals to productB and sumA equals to sumB then the arrays are permutations of each other. Else they are not permutations of each other.

Source Code

Analysis

Running Time : We traverse the array once in the first as well as the second loop. Hence the running time would be O(N).

Auxiliary Space
As we can see there is not much of extra space required, we only used eight extra variable for maintaining the counter.

Don’t forget to subscribe to TechieMe to get updates on latest posts.