Given an array A[ ] of positive integers of size N, where each value represents the number of chocolates in a packet. Each packet can have a variable number of chocolates. There are M students, the task is to distribute chocolate packets among M students such that :
1. Each student gets exactly one packet.
2. The difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student is minimum.
Example 1:
Input:
N = 8, M = 5
A = {3, 4, 1, 9, 56, 7, 9, 12}
Output: 6
Explanation: The minimum difference between 
maximum chocolates and minimum chocolates 
is 9 - 3 = 6 by choosing following M packets :
{3, 4, 9, 7, 9}.
Example 2:
Input:
N = 7, M = 3
A = {7, 3, 2, 4, 9, 12, 56}
Output: 2
Explanation: The minimum difference between
maximum chocolates and minimum chocolates
is 4 - 2 = 2 by choosing following M packets :
{3, 2, 4}.
Your Task:
You don't need to take any input or print anything. Your task is to complete the function findMinDiff() which takes array A[ ], N and M as input parameters and returns the minimum possible difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student.
Expected Time Complexity: O(N*Log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{9}
1 ≤ M ≤ N

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #User function Template for python3



class Solution:



    def findMinDiff(self, A,N,M):



        # code here

Solutions:
class Solution:

	def findMinDiff(self, arr, n, m):
		if m == 0 or n == 0:
			return 0
		arr.sort()
		if n < m:
			return -1
		min_diff = arr[n - 1] - arr[0]
		for i in range(len(arr) - m + 1):
			min_diff = min(min_diff, arr[i + m - 1] - arr[i])
		return min_diff


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		ans = max(A) - min(A)
		for i in range(N - M + 1):
			if A[i + M - 1] - A[i] < ans:
				ans = A[i + M - 1] - A[i]
		return ans


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		c = 0
		min_c = A[N - 1] - A[0]
		for i in range(0, N - M + 1):
			c = A[i + M - 1] - A[i]
			if c < min_c:
				min_c = c
		return min_c


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		left = 0
		right = M - 1
		min_diff = float('inf')
		if M == 1:
			return 0
		while right < N and left < right:
			min_diff1 = A[right] - A[left]
			if min_diff1 < min_diff:
				min_diff = min_diff1
			left += 1
			right += 1
		return min_diff


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		count = 100000000
		for i in range(0, len(A)):
			if i + M > N:
				break
			temp = A[i + M - 1] - A[i]
			if temp < count:
				ans = temp
				count = temp
		return ans


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		min_diff = float('inf')
		for i in range(N - M + 1):
			diff = A[i + M - 1] - A[i]
			if diff < min_diff:
				min_diff = diff
		return min_diff


class Solution:

	def findMinDiff(self, A, N, M):
		A = sorted(A)
		mindiff = A[M - 1] - A[0]
		for i in range(N - M + 1):
			mindiff = min(mindiff, A[M - 1 + i] - A[i])
		return mindiff


class Solution:

	def findMinDiff(self, A, N, M):
		if M > N:
			retutn - 1
		A.sort()
		min_dif = float('inf')
		for i in range(N - M + 1):
			dif = A[i + M - 1] - A[i]
			if dif < min_dif:
				min_dif = dif
		return min_dif


class Solution:

	def findMinDiff(self, A, N, M):
		if M < 1 and N < 1:
			return 0
		A.sort()
		if N < M:
			return -1
		min_diff = A[N - 1] - A[0]
		for i in range(len(A) - M + 1):
			min_diff = min(min_diff, A[i + M - 1] - A[i])
		return min_diff


import sys

class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		minn = A[N - 1] - A[0]
		for i in range(0, N - M + 1):
			minn = min(minn, A[i + M - 1] - A[i])
		return minn


class Solution:

	def findMinDiff(self, A, N, M):
		A = sorted(A)
		if N == 0 or M == 0:
			return 0
		if M > N:
			return -1
		diff = A[N - 1] - A[0]
		for i in range(N - M + 1):
			diff = min(diff, A[i + M - 1] - A[i])
		return diff


class Solution:

	def findMinDiff(self, A, N, M):
		if M == 0 or N == 0:
			return 0
		A.sort()
		i = 0
		j = M - 1
		min_diff = A[N - 1] - A[0]
		while j < N:
			min_diff = min(A[j] - A[i], min_diff)
			i += 1
			j += 1
		return min_diff


class Solution:

	def findMinDiff(self, A, N, M):
		if M == 0 or N == 0:
			return 0
		A.sort()
		if N < M:
			return -1
		min_diff = A[N - 1] - A[0]
		for i in range(N - M + 1):
			if A[i + M - 1] - A[i] < min_diff:
				min_diff = A[i + M - 1] - A[i]
		return min_diff


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		return min([A[i + M - 1] - A[i] for i in range(N - M + 1)])


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		l = []
		for i in range(0, M):
			l.append(A[i])
		m = abs(l[0] - l[-1])
		j = 0
		for i in range(M, N):
			l.pop(j)
			l.append(A[i])
			m = min(m, abs(l[0] - l[-1]))
		return m


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		mn = A[0]
		mx = A[M - 1]
		mini_diff = mx - mn
		for i in range(M, N):
			mn = A[i - M + 1]
			mx = A[i]
			mini_diff = min(mini_diff, mx - mn)
		return mini_diff


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		minimum = max(A)
		n = N - M + 1
		for i in range(n):
			if A[i + M - 1] - A[i] < minimum:
				minimum = A[i + M - 1] - A[i]
		return minimum


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		i = 0
		j = M - 1
		MM = 10000000
		for k in range(N - M + 1):
			if A[j] - A[i] < MM:
				MM = A[j] - A[i]
			i += 1
			j += 1
		return MM


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		min_choc = 0
		max_choc = 0 + M - 1
		min_diff = A[max_choc] - A[min_choc]
		while max_choc < N:
			curr_diff = A[max_choc] - A[min_choc]
			if curr_diff < min_diff:
				min_diff = curr_diff
			min_choc += 1
			max_choc += 1
		return min_diff


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		if N == M:
			return A[-1] - A[0]
		else:
			min_diff = A[-1] - A[0]
			for i in range(N):
				if i + M - 1 < N:
					min_cur = A[i + M - 1] - A[i]
					min_diff = min(min_diff, min_cur)
			return min_diff


class Solution:

	def findMinDiff(self, a, n, m):
		a.sort()
		r = a[n - 1]
		for i in range(0, n - m + 1):
			r = min(r, a[i + m - 1] - a[i])
		return r


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		ans = 100000000000000
		for i in range(N - M + 1):
			ans1 = A[M - 1 + i] - A[i]
			ans = min(ans, ans1)
		return ans


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		if N == M:
			return A[N - 1] - A[0]
		min_diff = max(A)
		for i in range(N - M + 1):
			j = i + M - 1
			min_so_far = A[j] - A[i]
			min_diff = min(min_diff, min_so_far)
		return min_diff


class Solution:

	def findMinDiff(self, arr, N, M):
		arr.sort()
		ans = arr[-1] - arr[0]
		for i in range(N - M + 1):
			ans = min(ans, arr[i + M - 1] - arr[i])
		return ans


from itertools import permutations

class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		ans = A[-1]
		for i in range(N - M + 1):
			ans = min(ans, A[i + M - 1] - A[i])
		return ans


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		a = 0
		b = M - 1
		c = 999999999
		while b <= N - 1:
			if A[b] - A[a] < c:
				c = A[b] - A[a]
			a += 1
			b += 1
		return c


import sys

class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		minAns = sys.maxsize - 1
		right = M - 1
		left = 0
		diff = 0
		while right <= N - 1:
			diff = A[right] - A[left]
			left += 1
			right += 1
			minAns = min(diff, minAns)
		return minAns


class Solution:

	def findMinDiff(self, A, N, M):
		ans = 9999999999999999999999
		A.sort()
		for i in range(0, len(A) - M + 1):
			if ans > A[M - 1 + i] - A[i]:
				ans = A[M - 1 + i] - A[i]
		return ans


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		first = 0
		min = max(A)
		while first + M - 1 < N:
			if A[first + M - 1] - A[first] < min:
				min = A[first + M - 1] - A[first]
			first += 1
		return min


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		diff = 0
		mindiff = float('inf')
		for i in range(N - M + 1):
			j = i + (M - 1)
			diff = A[j] - A[i]
			mindiff = min(mindiff, diff)
		return mindiff


class Solution:

	def findMinDiff(self, A, N, M):
		A = sorted(A)
		i = 0
		mn = float('inf')
		for j in range(M - 1, N):
			mn = min(mn, A[j] - A[i])
			i += 1
		return mn


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		mn = 99999
		i = 0
		while i + M - 1 < N:
			mn = min(mn, A[i + M - 1] - A[i])
			i += 1
		return mn


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		mn = A[M - 1] - A[0]
		i = 0
		j = M - 1
		while j < N:
			if A[j] - A[i] < mn:
				mn = A[j] - A[i]
			i += 1
			j += 1
		return mn


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		m = 1000000000000
		for i in range(N - M + 1):
			r = A[M + i - 1] - A[i]
			m = min(m, r)
		return m


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		mi = 10000000001
		if N == M:
			return A[-1] - A[0]
		for i in range(N - M + 1):
			s = A[i + M - 1] - A[i]
			mi = min(mi, s)
		return mi


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		j = M - 1
		i = 0
		s = 100000
		while j < N:
			s = min(A[j] - A[i], s)
			(i, j) = (i + 1, j + 1)
		return s


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		mini = float('inf')
		start = 0
		end = M - 1
		while end < N:
			diff = A[end] - A[start]
			mini = min(mini, diff)
			start += 1
			end += 1
		return mini


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		start = 0
		i = M - 1
		mini = 10 ** 9
		while i < N:
			mini = min(mini, A[i] - A[start])
			start += 1
			i += 1
		return mini


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		min_diff = float('inf')
		i = 0
		j = M - 1
		while j < N:
			diff = A[j] - A[i]
			if diff < min_diff:
				min_diff = diff
			i += 1
			j += 1
		return min_diff


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		mini = 0
		maxi = M - 1
		diff = A[maxi] - A[mini]
		for i in range(M, N):
			mini += 1
			maxi += 1
			diff = min(diff, A[maxi] - A[mini])
		return diff


import sys

class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		i = 0
		j = M - 1
		mini = sys.maxsize
		while j < N:
			diff = A[j] - A[i]
			mini = min(mini, diff)
			i += 1
			j += 1
		return mini


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		mini = max(A)
		i = 0
		while i + M - 1 != N:
			s = A[i + M - 1] - A[i]
			mini = min(mini, s)
			i += 1
		return mini


class Solution:

	def findMinDiff(self, A, N, M):
		A = sorted(A)
		s = A[0]
		e = A[M - 1]
		o = e - s
		for i in range(1, N - M + 1):
			s = A[i]
			e = A[M - 1 + i]
			o = min(o, e - s)
		return o


import math

class Solution:

	def findMinDiff(self, A, N, M):
		mindiff = math.inf
		A = sorted(A)
		windowstart = 0
		windowend = 0
		for windowend in range(len(A)):
			if windowend >= M - 1:
				mindiff = min(mindiff, A[windowend] - A[windowstart])
				windowstart += 1
		return mindiff


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort(reverse=True)
		l = 0
		r = M - 1
		res = A[l] - A[r]
		while r < N:
			res = min(res, A[l] - A[r])
			l += 1
			r += 1
		return res


class Solution:

	def findMinDiff(self, A, N, M):
		A = sorted(A)
		i = 0
		min = 9999999
		while i + M - 1 < N:
			k = i + M - 1
			if A[k] - A[i] < min:
				min = A[k] - A[i]
			i += 1
		return min


class Solution:

	def findMinDiff(self, A, N, M):
		i = 0
		j = M - 1
		d = max(A)
		A.sort()
		while j < N:
			d = min(d, A[j] - A[i])
			i += 1
			j += 1
		return d


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		diff = 0
		ans = 9999999999
		for i in range(N - M + 1):
			diff = A[i + M - 1] - A[i]
			if diff < ans:
				ans = diff
		return ans


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		i = 0
		res = 0
		while i <= N - M:
			k = A[i + M - 1] - A[i]
			if i == 0:
				res = k
			else:
				res = min(res, k)
			i += 1
		return res


import sys

class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		maxd = sys.maxsize
		for i in range(N - M + 1):
			maxd = min(maxd, A[i + M - 1] - A[i])
		return maxd


class Solution:

	def findMinDiff(self, A, N, M):
		if N == 1:
			return A[0]
		A.sort()
		(l, r) = (0, M - 1)
		diff = float('inf')
		while r < N:
			x = A[r] - A[l]
			diff = min(x, diff)
			l += 1
			r += 1
		return diff


import numpy as np

class Solution:

	def findMinDiff(self, A, N, M):
		A_sorted = sorted(A)
		min_diff = np.inf
		for i in range(0, N - M + 1):
			diff = A_sorted[i + M - 1] - A_sorted[i]
			if diff < min_diff:
				min_diff = diff
		return min_diff


import sys

class Solution:

	def findMinDiff(self, A, N, M):
		[1, 3, 4, 7, 9, 9, 12, 56]
		res = sys.maxsize
		A.sort()
		for i in range(N - M + 1):
			if A[i + M - 1] - A[i] < res:
				res = A[i + M - 1] - A[i]
		return res


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		i = 0
		j = M - 1
		min_ans = float('inf')
		while j < N:
			temp_min = A[j] - A[i]
			min_ans = min(temp_min, min_ans)
			i += 1
			j += 1
		return min_ans


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		ans = 999999999
		for i in range(N - M + 1):
			if A[i] == 0:
				continue
			ans = min(ans, A[i + M - 1] - A[i])
		return ans


class Solution:

	def findMinDiff(self, A, N, M):
		A.sort()
		i = 1
		j = M
		diff = A[M - 1] - A[0]
		while j < N:
			diff = min(diff, A[j] - A[i])
			i += 1
			j += 1
		return diff


class Solution:

	def findMinDiff(self, A, N, M):
		A = sorted(A)
		_i = 0
		_res = max(A) + 1
		while _i + M - 1 < N:
			_res = min(_res, A[_i + M - 1] - A[_i])
			_i += 1
		return _res


class Solution:

	def findMinDiff(self, arr, n, m):
		arr.sort()
		mini = arr[-1] - arr[0]
		for i in range(n - m + 1):
			mini = min(mini, arr[i + m - 1] - arr[i])
		return mini


class Solution:

	def findMinDiff(self, arr, n, m):
		arr = sorted(arr)
		l = 0
		r = m - 1
		mn = 10 ** 9 + 1
		while r < n:
			if arr[r] - arr[l] < mn:
				mn = arr[r] - arr[l]
			l += 1
			r += 1
		return mn