The distance of an element A[i] in an unsorted array is |i j| with j the place o

ID: 3761077 • Letter: T

Question

The distance of an element A[i] in an unsorted array is |i j| with j the place of A[i] in the sorted array. For example, in the array 6, 4, 2, 3, 8 the distance of 8 is 0 (8 is in its proper place), the distance of 6 is 3 (6 is now first in the order but should be forth), the distance of 4 is 1, the distance of 2 is 2 and the distance of 3 is 2.

Show an input where the sum of distances is (n 2 )

In the algorithm, always explain how and why they work. ALWAYS, analyze the complexity of an algorithm. In all algorithms, always try to get the fastest possible. In all data structures, try to minimize as much as possible the running time of any operation.

Explanation / Answer

Use two loops: The outer loop picks all the elements of arr[] one by one. The inner loop picks all the elements after the element picked by outer loop. If the elements picked by outer and inner loops have same values as x or y then if needed update the minimum distance calculated so far.

#include <stdio.h>

#include <stdlib.h> // for abs()

#include <limits.h> // for INT_MAX

int minDist(int arr[], int n, int x, int y)

{

int i, j;

int min_dist = INT_MAX;

for (i = 0; i < n; i++)

{

for (j = i+1; j < n; j++)

{

if( (x == arr[i] && y == arr[j] ||

y == arr[i] && x == arr[j]) && min_dist > abs(i-j))

{

min_dist = abs(i-j);

}

return min_dist;

}

/* Driver program to test above fnction */

int main()

{

int arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3};

int n = sizeof(arr)/sizeof(arr[0]);

int x = 3;

int y = 6;

printf("Minimum distance between %d and %d is %d ", x, y,

minDist(arr, n, x, y));

return 0;

}

Output: Minimum distance between 3 and 6 is 4

Time Complexity: O(n^2)