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 ?

4
Contributors
4
Replies
5
Views
5 Years
Discussion Span
Last Post by np complete

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.

The Chef needs to pick 2 horses

Is he cooking them, or making a wager?

Sorry.

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 topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.