Menu
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.
854
A simple solution for this problem is to, one by one, pick each element from the array and find its first and last occurrence in the array and take the difference between the first and last occurrence for maximum distance. The time complexity for this approach is O(n2).
In this method, we first initialize two numpy arrays. Then, we take the difference of the two arrays, compute the dot product of the result, and transpose of the result. Then we take the square root of the answer. This is another way to implement Euclidean distance.
Use the math. dist() Function to Find the Euclidean Distance Between Two Points. The math module also can be used as an alternative. The dist() function from this module can return the line segment between two points.
Distance formula: d = sqrt{ (x_2 - x_1)^2 + (y_2 - y_1)^2 }
You can get a O(MlogM) complexity solution in the following way.
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.
54
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
