PROBLEM LINK:
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.