# EID Editorial

Tester: Hussain Kara Fallah
Editorialist: Hussain Kara Fallah

### PROBLEM

Chef has N coins. Each coin has a value. Chef has 2 children whom he will give 1 coin to each. He wants the difference between this two coins to be minimum possible. You need to help Chef and check what’s the minimum possible difference.

Easy

### EXPLANATION

If you suppose that you are giving 1 coin to one of the children. To make the difference minimum as possible you need to give the other child the smallest coin which has a bigger value than the first, or the biggest coin which has a smaller value. (Of course there maybe 2 coins with the same value then the answer is zero).

Sort the coins according to their values, and check the difference between every 2 consecutive coins in the sorted array. To fit into the time limit you need to use a fast sorting algorithm (Quicksort , MergeSort). You can also use built-in sort functions in some languages (C++,Java…).

Complexity : O(N log N)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s/Editorialist’s solution can be found here.

I think that using a quicker sorting method is really in-effective, because that tests the sorting knowledge more than the competitive knowledge. I think I have a better solution, which does not use sorting techniques. Do check

``````# -*- coding: utf-8 -*-
"""
Created on Mon Dec 16 15:28:58 2019

@author: tanma
"""

t=int(input())
for _ in range(t):
n=int(input())
a=input().split()
a=[int(i) for i in a]
_max=0
_min=10**7
for i in a:
if _max < i:
_max=i
if _min > i:
_min = i

x=[0]*(_max+1)
for i in a:
x[i]+=1

min_diff=10**7
if x[_min]>1:
min_diff=0

if min_diff != 0:

for i in range(_min+1, _max):
if x[i]==0:
continue
if x[i]>1:
min_diff=0
break

diff=i - _min
if diff < min_diff:
min_diff=diff
_min = i
if x[_max]>1:
min_diff=0

print(min_diff)
``````