Skills101
← All coding problems

Chocolate Distribution

mediumPlacement Coding+20 XPTime limit 2s

There are n packets of chocolates; packet i has a[i] chocolates. Give exactly one packet to each of m students so that the difference between the largest and smallest packet given out is as small as possible. Print that smallest difference.

Input:

  • line 1: n m
  • line 2: n integers

Output: the minimum possible difference.

Constraints: 1 ≤ m ≤ n ≤ 10⁵, 0 ≤ a[i] ≤ 10⁹.

Think about it: after sorting, the best choice is always m packets that sit next to each other. Slide a window of size m and take the smallest a[i + m − 1] − a[i].

Sample input 1

8 5
3 4 1 9 56 7 9 12

Sample output 1

6

Sample input 2

7 3
7 3 2 4 9 12 56

Sample output 2

2

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.