CODEWITHSUNDEEP
arraysalgorithm
Karsten Ari Agathon
Karsten Ari Agathon

Reputation: 123

Find all possible distances from two arrays

Given two sorted array A and B length N. Each elements may contain natural number less than M. Determine all possible distances for all combinations elements A and B. In this case, if A[i] - B[j] < 0, then the distance is M + (A[i] - B[j]).

Example :

A = {0,2,3}
B = {1,2}
M = 5

Distances = {0,1,2,3,4}

Note: I know O(N^2) solution, but I need faster solution than O(N^2) and O(N x M).

Edit: Array A, B, and Distances contain distinct elements.

Upvotes: 6

Views: 184

Answers (3)

Dave
Dave

Reputation: 9065

You can use bitvectors to accomplish this. Bitvector operations on large bitvectors is linear in the size of the bitvector, but is fast, easy to implement, and may work well given your 50k size limit.

Initialize two bitvectors of length M. Call these vectA and vectAnswer. Set the bits of vectA that correspond to the elements in A. Leave vectAnswer with all zeroes.

Define a method to rotate a bitvector by k elements (rotate down). I'll call this rotate(vect,k).

Then, for every element b of B, vectAnswer = vectAnswer | rotate(vectA,b).

Upvotes: 0

Анатолий
Анатолий

Reputation: 2857

I possible done with optimized N*N.

If convert A to 0 and 1 array where 1 on positions which present in A (in range [0..M]. After convert this array into bitmasks, size of A array will be decreased into 64 times.

This will allow insert results by blocks of size 64. Complexity still will be N*N but working time will be greatly decreased. As limitation mentioned by author 50000 for A and B sizes and M. Expected operations count will be N*N/64 ~= 4*10^7. It will passed in 1 sec.

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33499

You can get a O(MlogM) complexity solution in the following way.

  1. Prepare an array Ax of length M with Ax[i] = 1 if i belongs to A (and 0 otherwise)
  2. Prepare an array Bx of length M with Bx[M-1-i] = 1 if i belongs to B (and 0 otherwise)
  3. Use the Fast Fourier Transform to convolve these 2 sequences together
  4. Inspect the output array, non-zero values correspond to possible distances

Note that the FFT is normally done with floating point numbers, so in step 4 you probably want to test if the output is greater than 0.5 to avoid potential rounding noise issues.

Upvotes: 5

Related Questions