Find the minimum distance between two numbers

CODE

Find the minimum distance between two numbers

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[].

Method 1 (Simple)

#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\n", x, y,

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

    return 0;

}

Output:

Minimum distance between 3 and 6 is 4

Method 2 (Tricky)

#include <stdio.h>

#include <limits.h>  // For INT_MAX

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

{

   int i = 0;

   int min_dist = INT_MAX;

   int prev;

   // Find the first occurence of any of the two numbers (x or y)

   // and store the index of this occurence in prev

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

   {

     if (arr[i] == x || arr[i] == y)

     {

       prev = i;

       break;

     }

   }

   // Traverse after the first occurence

   for ( ; i < n; i++)

   {

      if (arr[i] == x || arr[i] == y)

      {

          // If the current element matches with any of the two then

          // check if current element and prev element are different

          // Also check if this value is smaller than minimm distance so far

          if ( arr[prev] != arr[i] && (i - prev) < min_dist )

          {

             min_dist = i - prev;

             prev = i;

          }

          else

             prev = i;

      }

   }

   return min_dist;

}

/* Driver program to test above fnction */

int main()

{

    int arr[] ={3, 5, 4, 2, 6, 3, 0, 0, 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\n", x, y,

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

    return 0;

}

Output:

Minimum distance between 3 and 6 is 1

Examples:

Input: arr[] = {1, 2}, x = 1, y = 2

Output: Minimum distance between 1 and 2 is 1.

Input: arr[] = {3, 4, 5}, x = 3, y = 5

Output: Minimum distance between 3 and 5 is 2.

Input: arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6

Output: Minimum distance between 3 and 6 is 4.

Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2

Output: Minimum distance between 3 and 2 is 1.