CODEWITHSUNDEEP
c
newby
newby

Reputation: 189

Shortest difference between elements of an array

I am new to online judges. I solved a problem getting correct output on my PC but online judge is directly saying wrong answer.

Here is the problem https://www.codechef.com/problems/HORSES

This question deals with only shortest difference between elements of array.

My solution may not be efficient but it is correct.

Please help me

Chef is very fond of horses. He enjoys watching them race. As expected, he has a stable full of horses. He, along with his friends, goes to his stable during the weekends to watch a few of these horses race. Chef wants his friends to enjoy the race and so he wants the race to be close. This can happen only if the horses are comparable on their skill i.e. the difference in their skills is less.

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

You can read the problem here https://www.codechef.com/problems/HORSES

#include<stdio.h>
#include<limits.h>
int main(){
    int t,n,i,u,v;
    int min=INT_MAX;
    scanf("%d",&t);
    while(t>0){
        scanf("%d",&n);
        int *s=malloc(sizeof(int)*n);
        for(i=0;i<n;i++){
            scanf("%d",&s[i]);
        }
        for(i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(min>abs(s[i]-s[j]))
                    min=abs(s[i]-s[j]);

            }

        }
    printf("%d\n",min);
    t--;

   }
}

Upvotes: 1

Views: 675

Answers (1)

chux
chux

Reputation: 153498

I solved a problem getting correct output on my PC but online judge is directly saying wrong answer.

Insufficient testing. Code is correct when t ==1, yet not for t > 1.

Code needs to reset the minimum for each test case.

// int min=INT_MAX;
scanf("%d",&t);
while(t>0){
  int min = INT_MAX; // add

Other short-comings exists too, yet the above is key.
Robust code would:

  1. Check the return value of scanf()

  2. Check that malloc() succeeded and then later free it.

  3. Address potential; overflow in abs(s[i]-s[j])

Also

  1. Consider delaying variable declaration to the block that needs it. Had OP done this, the above problem would not have occurred.

  2. Format code more uniformly and use {} even with single line blocks with for, if, ....

Efficiency

Sort the array first (qsort()) and then walk the array noting difference between elements. O(n*lg(n))

Upvotes: 1

Related Questions