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.

  • Jani Kettunen

    Hi, unfortunately this solution seems to fail for the following input: [4 4 9 2 4 9 2 4] and [8 2 3 3 8 3 3 8]

    • Hey, Thanks for bringing into notice. This is not the correct solution. You can post one if you have, else I will update this post soon.

      • Jani Kettunen

        I don't know any non-probabilistic linear time algorithms for this. There's some interesting discussion at mathoverflow: http://mathoverflow.net/questions/25374/duplicate-detection-problem/25419#25419

      • Игорь Писарев

        Actually, there are lots of simpler failure inputs, for example [4 4 9] and [3 6 8]

        Jani +1, it can't be done with the mentioned complexity
        This problem is equivalent to the existence of a multiset fingerprinting function
        (even if all the numbers were distinct, such fingerprinting function is a sum of powers of these numbers which overflows very fast, and it's generally requires O(log n) to calculate a power of 2 a particular number)

        • True… I realized that we need to make the edit to this post. Thanks for your useful comments.

          • Roushan

            /* package whatever; // don't place package name! */

            import java.util.*;

            import java.lang.*;

            import java.io.*;

            /* Name of the class has to be "Main" only if the class is public. */

            class Ideone

            {

            public static void main (String[] args) throws java.lang.Exception

            {

            int a[]={4 ,4, 9};

            int b[]={8,3,6};

            int aZeroes = 0;

            int bZeroes = 0;

            int aOnes = 0;

            int bOnes = 0;

            int sumA = 0;

            int productA = 1;

            int sumSquareA=0;

            int sumB = 0;

            int productB = 1;

            int sumSquareB=0;

            for (int i = 0; i < a.length; i++) {

            if (a[i] == 0) {

            aZeroes++;

            } else if (a[i] == 1) {

            sumA += a[i];

            sumSquareA=sumSquareA+a[i]*a[i];

            aOnes++;

            } else {

            sumA += a[i];

            productA *= a[i];

            sumSquareA=sumSquareA+a[i]*a[i];

            }

            }

            for (int i = 0; i < b.length; i++) {

            if (b[i] == 0) {

            bZeroes++;

            } else if (b[i] == 1) {

            sumB += b[i];

            sumSquareB=sumSquareB+a[i]*a[i];

            bOnes++;

            } else {

            sumB += b[i];

            sumSquareB=sumSquareB+b[i]*b[i];

            productB *= b[i];

            }

            }

            System.out.println(sumSquareA);

            System.out.println(sumSquareB);

            if(aZeroes == bZeroes && aOnes == bOnes && sumA == sumB && productA == productB && sumSquareA==sumSquareB)

            System.out.println("PREMUTATION");

            else

            System.out.println("NOT PERMUTATION");

            // your code goes here

            }

            }