Numbers of common distinct difference

user_10013529 0
Viewed 178

Given two array A and B. Task to find the number of common distinct (difference of elements in two arrays). Example :

A=[3,6,8]
B=[1,6,10]

so we get differenceSet for A
differenceSetA=[abs(3-6),abs(6-8),abs(8-3)]=[3,5,2]
similiarly
differenceSetB=[abs(1-6),abs(1-10),abs(6-10)]=[5,9,4]

Number of common elements=Intersection :{differenceSetA,differenceSetB}={5}
Answer= 1

My approach O(N^2)

int commonDifference(vector<int> A,vector<int> B){
    int n=A.size();
    int m=B.size();
    unordered_set<int> differenceSetA;
    unordered_set<int> differenceSetB;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            differenceSetA.insert(abs(A[i]-A[j]));
        }
    }
    for(int i=0;i<m;i++){
        for(int j=i+1;j<m;j++){
            differenceSetB.insert(abs(B[i]-B[j]));
        }
    }
    int count=0;
    for(auto &it:differenceSetA){
        if(differenceSetB.find(it)!=differenceSetB.end()){
            count++;
        }
    }
    return count;
    
}

Please provide suggestions for optimizing the approach in O(N log N)

c++17 data-structures set algorithm c++
1 Answers

If n is the maximum range of a input array, then the set of all differences of a given array can be obtained in O(n logn), as explained in this SO post: find all differences in a array

Here is a brief recall of the method, with a few additional practical implementation details:

  1. Create an array Posi of length 2*n = 2*range = 2*(Vmax - Vmin + 1), where elements whose index matches an element of the input are set to 1, other elements are set to 0. This can be created in O(m), where m is the size of the array.
    For example, given in input array [1,4,5] of size m, we create an array [1,0,0,1,1].
Initialisation: Posi[i] = 0 for all i (i = 0 to 2*n)
Posi[A[i] - Vmin] = 1 (i = 0 to m)
  1. Calculate the autocorrelation function of array Posi[]. This can be classically performed in three sub-steps

2.1 Calculate the FFT (size 2*n) of Posi[]array: Y[] = FFT(Posi)

2.2 Calculate the square amplitude of the result: Y2[k] = Y[k] * conj([Y[k])

2.3 Calculate the Inverse FFT of the result Diff[] = IFFT (Y2[])`

A few details are worth being mentioned here:

  • The reason why a size 2*n was selected, and not a size n, if that, is d is a valid difference, then -d is also a valid difference. The results corresponding to negative differences are available at positions i >= n
  • If you find more easy to perform FFT with a size a-power-of-two, than you can replace the size 2*n with a value n2k = 2^k, with n2k >= 2*n
  1. The non-null differences correspond to non-null values in the array Diff[]:
`d` is a difference if `Diff[d] > 0`

Another important details is that a classical FFT is used (float calculations), then you encounter little errors. To take it into account, it is important to replace the IFFT output Diff[] with integer rounded values of the real part.

All that concerns one array only. As you want to calculate the number of common differences, then you have to:

  • calculate the arrays Diff_A[] and Diff_B[] for both sets A and B and then:
count = 0;
if (Diff_A[d] != 0) and (Diff_B[d] != 0) then count++;

A little Bonus

In order to avoid a plagiarism of the mentioned post, here is an additional explanation about the way to get the differences of one set, with the help of the FFT.

The input array A = {3, 6, 8} can mathematically be represented by the following z transform:

 A(z) = z^3 + z^6 + z^8

Then the corresponding z-transform of the difference array is equal to the polynomial product:

D(z) = A(z) * A(z*) = (z^3 + z^6 + z^8) (z^(-3) + z^(-6) + z^(-8)) 
= z^(-5) + z^(-3) + z^(-2) + 3 + z^2 + z^3 + z^5

Then, we can note that A(z) is equal to a FFT of size N of the sequence [0 0 0 1 0 0 1 0 1] by taking:

z = exp (-i * 2 PI/ N), with i = sqrt(-1)

Note that here we consider the classical FFT in C, the complex field.

It is certainly possible to perform calculation in a Galois field, and then no rounding errors, as it is done for example to implement "classical" multiplications (with z = 10) for a large number of digits. This seems over-skilled here.

user_105533410
Related