EID Editorial

general
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
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.

DIFFICULTY

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.

2

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)