The Interview Question Today#14(9-3-19)

Question
Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. The array might also contain duplicates. You may assume that both x and y are different and present in arr[].

Examples:
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 and 2 is 1.

Solution

Approach:

ALGORITHM MinDistance(A[0..n - 1])

//Input: Array A[0..n - 1] of numbers

//Output: Minimum distance between two of its elements

dmin ← ∞

for i ← 0 to n - 1 do

forj ← 0 to n - 1 do

ifi = j and |A[i] - A[j]| < dmin

dmin← |A[i] - A[j]|

return dmin

C program:

// C program to Find the minimum// distance between two numbers

#include <stdio.h>

#include <stdlib.h> // for abs() Which calculate the difference between the //location in array 

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

{

   int i, j;

   int min_dist =30000;

   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;

}

int main()

{

    int arr[100];

    int n,i;

    int x;

    int y;

printf("Enter the no elements required in array\n ");

scanf("%d",&n);

printf("Enter the elements\n");

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

{

    scanf("%d",&arr[i]);

 }

printf("Enter the elements whose distance u want\n");

scanf("%d %d",&x,&y);

printf("Minimum distance between %d and %d is %d\n",x, y,minDist(arr, n, x, y));

    return 0;

} 

Output:

Enter the no elements required in array

 5

Enter the elements

1

2

3

4

5

Enter the elements whose distance u want

2

5

Minimum distance between 2 and 5 is 3