Horse Racing

[np complete]

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 ?

[mrnutty]

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.

[Suzie999]

The Chef needs to pick 2 horses

Is he cooking them, or making a wager?

Sorry.

[NathanOliver]

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.

[np complete]

@ NathanOliver

I will get rid of those lines.

@firstPerson

Can you suggest some materials for hashmaps as you said.