[Problem Solving #1] Project Team (InMobi Challenge question)

A Professor of Physics gave projects to the students of his class. The students have to form a team of two for doing the project. The professor left the students to decide the teams. The number of students in a class will be even.
Each student has a knowledge level. It tells how much knowledge each student has. The knowledge level of a team is the sum of the knowledge levels of both the students.The students decide to form groups such that the difference between the team with highest knowledge and the one with lowest knowledge is minimum.InputFirst line of the input will contain number of test cases t; In the next t lines the first number is n the number of students in the class followed by n integers denoting the knowledge levels of the n studentsOutputYour output should be a single line containing the lowest possible difference between the team with highest knowledge and the one with lowest knowledge.

Sample Input

2
4 2 6 4 3
6 1 1 1 1 1 1

Sample Output

1
0

Explanation

Input Constraints are

1 <= t <= 100
1 <= n <= 100
1 <= knowledge level <= 10000

Program in C:

1. #include <stdio.h>
2. #include <stdlib.h>
3. 
   
4. int comp(const void *a,const void *b) {
5.        int *x = (int *) a;
6.        int *y = (int *) b;
7. return *x - *y;
8. }
9. 
   
10. int find_team_gk(int student_gk[], int count){
11.   int start=0, end=count-1;
12. int team_gk[(start+end+1)/2];
13. int t;
15. qsort(student_gk, count, sizeof(int), comp);
16. for (t=0; start+1<=end;t++) {
17. team_gk[t] = student_gk[start] + student_gk[end];
18. start++;
19. end--;
20. }
21. if (team_gk[0] > team_gk[1]) 
22. return (team_gk[0] - team_gk[1]);
23. else
24. return (team_gk[1] - team_gk[0]);
25. }
26. 
    
27. int main()
28. {
29. int testcases, students;
30.   int *student_gk, *output;
31.   int i, s;
32. 
    
33. printf("number of testcases:");
34. scanf("%d", &testcases);
35. output = (int *)malloc(testcases * sizeof(int));
36. 
    
37.    for (i=0; i< testcases; i++) {
38. printf("Enter number of students and their gk level in order:"):
39.      scanf("%d", &students);
40.      student_gk = (int *)malloc(students * sizeof(int));
41.      for (s=0; s<students; s++) {
42.      scanf("%d", &student_gk[s]);
43.      }
44.      }
45.       for (i=0; i<testcases; i++)
46. output[i] = find_team_gk(student_gk, students);
47. 
    
48.  for (i=0; i<testcases; i++)
49.      printf("%d\n", output[i]);
50. return 0;
51. }
52.