Check if two arrays are similar

Question

Given two arrays, check if they're similar (i.e. have the same integers and each integer occurs same number of times).

For example:

int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}

I was not allowed to use sorting and hashtable. It should be O(n) and should not use any extra space.

This was an interview question.

Tried with rules like:

1. Sum of integers in two arrays should be same
2. Product of integers in two arrays should be same.
3. XOR of all integers should be zero

But still interviewer is not happy. Maybe I'm missing some corner cases.

Answer 1

I can think of one way to perform this task, if the elements values are integers and bounded by n (1...n), where n is the size of the arrays (this applies to you example):

In each array, for each element x, we do arr[x%(n+1)-1] += n+1. we use mod since the element may vary through the process, by using mod we get the element that appeared in the original array.

What we do is count the number of appearances of a value v in arr[v] by adding n+1, then we can get the original value by doing arr[v]%(n+1) as the value is bounded by n, and the number of appearances by doing arr[v]/(n+1).

In the end we compare the number of appearances of each value in A and B, if for any value they are different, we return false. if the counting was the same for all the values, we return true.

This is an O(n) time solution that requires O(1) memory.

Here's the algorithm:

bool checkIfArraysAreSimilar(int[] A, int[] B)
{
    n = A.length; // = B.length
    int i;

    for (i = 0; i < n; i++)
    {
        A[(A[i]%(n+1))-1] += n+1;
        B[(B[i]%(n+1))-1] += n+1;
    }

    for (i = 0; i < n; i++)
    {
        if (A[i] / n+1 != B[i] / n+1)
            return false;
    }

    return true;
}

Answer 2

Try this Algorithm in JavaScript :

DEMO

var arr11 = [ 3, 5, 2, 5, 2]
var arr22 = [ 2, 3, 5, 5, 2]
console.log(arraySimilar(arr11,arr22));
function arraySimilar(arr1,arr2){ 
    var tempArr = arr2;
    // Checking Length if both the arrays are equal 
    if(arr1.length == arr2.length){
        //Running a For Loop for first array 
        for(i=0; i<arr1.length; i++){
            //If the Element is present removing from "tempArr"
            if(tempArr.indexOf(arr1[i])!= -1){
                tempArr.splice(tempArr.indexOf(arr1[i]),1);
            }
            else{ return false;}
        }
    }
    else{ return false; }
    // Check "tempArr" if it is empty
    if(tempArr.length==0){
        return true;
    }else{
        return false;
    }
}

Answer 3

Probably he means that you should compare sum by i of f(x[i]) and sum by i of f(y[i]), where x and y are the arrays, f is a hash function.

Answer 4

There are two possible ways for the first array whether it contains non repeated elements or not. let's say for simplicity the first array doesn't contain repeated elements, then the idea is very simple track the total as in my following code

#include <iostream>

int  main()
{ 
    int arr1[5] = { 1, 2, 3, 4, 5};
    int arr2[5] = { 5, 1, 3, 4, 2};

    int total(0);

    for (unsigned int i(0); i < 5; ++i)
    {
        for (unsigned int j(0); j < 5; ++j)
        {
            if ( arr1[i] == arr2[j] )
            {
                total += 1;
            }
        }
    }
    if ( total == 5 ) 
        std::cout << "Same " << std::endl;
    else 
        std::cout << "not Same " << std::endl;

    std::cin.get();
    return 0;
}

If the total is less than or greater than 5, then the arrays are not same. Now, it seems to me that we need to come up with an algorithm that calculates the proper total, so we need a function that accepts an array and check the total number. For example, in your case the total number should be 9 (1 for 3, 4 for 2, and 4 for 5). This is what came up to my mind. I hope the idea is clear. This is what I did for a general case

#include <iostream>


int getTotal(int arr[], const int size)
{
    int *temp = new int[size]; 
    int total(0);
    for (int i(0); i < size; ++i)
        temp[i] = arr[i];


    for (int i(0); i < size; ++i)
    {
        for (int j(0); j < size; ++j)
        {
            if ( arr[i] == temp[j] )
                total += 1;
        }
    }

    std::cout << total << std::endl;
    return total;
}

int  main()
{ 
    int arr1[5] = { 3, 5, 2, 5, 2};
    int arr2[5] = { 2, 3, 5, 5, 2};

    int total = getTotal(arr1, 5);
    int track(0);

    for (unsigned int i(0); i < 5; ++i)
    {
        for (unsigned int j(0); j < 5; ++j)
        {
            if ( arr1[i] == arr2[j] )
            {
                track += 1;
            }
        }
    }
    if ( track == total ) 
        std::cout << "Same " << std::endl;
    else 
        std::cout << "not Same " << std::endl;

    std::cin.get();
    return 0;
}

Another approach with using one loop. the idea is to get the total of an array and then divide the total by each element to get new total. If the new total of the first array is equal to the new total of the second array then, they are same. (Note: I haven't tested my code for all cases; however, my approach seems sensible to me.

#include <iostream>


double getTotal(double arr[], const int size)
{
    double total1(0), total2(0);

    for (int i(0); i < 5; ++i)
    {
        total1 += arr[i];
    }

    for (int i(0); i < 5; ++i)
    {
        total2 += total1/arr[i];
    }

    std::cout << total2 << std::endl;

    return total2;
}

int  main()
{ 
    double arr1[5] = { 3, 5, 2, 4, 2};
    double arr2[5] = { 2, 3, 5, 5, 2};

    double total1 = getTotal(arr1, 5);
    double total2 = getTotal(arr2, 5);

    if ( total1 == total2 ) 
        std::cout << "Same " << std::endl;
    else 
        std::cout << "not Same " << std::endl;

    std::cin.get();
    return 0;
}