There are N horses in the stable. The skill of the horse i is represented by an integer S[i]. The Chef needs to pick 2 horses for the race such that the difference in their skills is minimum. This way, he would be able to host a very interesting race. Your task is to help him do this and report the minimum difference that is possible between 2 horses in the race.
Input:
First line of the input file contains a single integer T, the number of test cases.
Every test case starts with a line containing the integer N.
The next line contains N space separated integers where the i-th integer is S[i].
Output:
For each test case, output a single line containing the minimum difference that is possible.
Constraints:

1 <= T <= 10
2 <= N <= 5000
1 <= S[i] <= 1000000000

Example:
Input:

1
5
4 9 1 32 13

Output:

3

Explanation: The minimum difference can be achieved if we pick horses with skills 1 and 4 for the race.

This is a problem from a site I found on net. Here is my solution.

# include <iostream>

using namespace std ;

void minimumDifference( long long * , int);

int fabs(int );

int main()
{
    int t, n, m = 0;
    long long s[5000];

    cin>>t;

    while( m < t )
    {

      cin>>n;

      for( int i = 0 ; i < n ; i++)
      {
          cin>>s[i];
      }

      minimumDifference(s,n);

      m++;
    }

    return 0;
}

int fabs(int x)
{
    if( x < 0)

       return -x;

    else

       return x;
}

void minimumDifference( long long *arr , int h)
{
    long long difference , smallest[h], f;

    for( int i = 0 ; i < h ; i++)
    {
        f = arr[i];

        difference = fabs(f - arr[ i+1 ]);

        for( int j = i+1; j < h-1 ; j++)
        {

            if(difference > fabs((f - arr[j])))
            {
                difference = fabs(f - arr[j]);
            }
        }

        smallest[i] = difference;
    }

    long long small;

    small =  smallest[0];

    for( int i = 0 ; i < h ; i++)
    {
        if( small > smallest[i])
        {
            small = smallest[i];
        }
    }

    cout<<small << endl;

    cin.get();
}

Is there something I'm missing in output ?

difference = fabs(f - arr[ i+1 ]);

That will be out of bounds in the case where i = (h-1) since arr[h] is not valid, because index stats at 0.

smallest[h]
You also shouldn't be allowed to create a variable sized static array.

Basically your algorithm is finding the smallest difference between position i against positions j, and for each position i, storing its minimum difference computed against position j in your smallest[h] array, then finding the minumim value in the smallest[h] array. That is a naive and simple way to solve this problem. After you get this working try to think of another way, possibly using hashmap or something.

You should be able to get rid of lines 64-77. If you just keep track of the smallest difference like you are already doing inside your second for loop you should be okay.

@ NathanOliver

I will get rid of those lines.

@firstPerson

Can you suggest some materials for hashmaps as you said.

This article has been dead for over six months. Start a new discussion instead.