you are given an array of size N. You need to select K elements from the array such that…
- User
you are given an array of size N. You need to select K elements from the array such that the difference between the max number among selected and the min number among selected array elements should be minimum. Print the minimum difference. INPUT: First line N number i.e., length of array Second line K number Next N lines contains a number for each line
OUTPUT: Print the minimum possible difference
0<N<10^5 0<K<N 0<number<10^9
SAMPLE INPUT 5 3 1 2 3 4 5
SAMPLE OUTPUT 2
Assistant
We are asked: "you are given an array of size N. You need to select K elements from the array such that the difference between the max number among selected and the min number among selected array elements should be minimum. Print the minimum difference."
This is classic: sort the array and then consider sliding window of length K, compute min difference of max - min in that window.
Input format: First line N, second line K, next N lines each a number.
Constraints: N up to 1e5, numbers up to 1e9. So O(N log N) works.
Thus solution: read N, K, array, sort, loop i from 0 to N-K, compute arr[i+K-1] - arr[i], keep min.
Edge cases: N=K? Then diff = max-min = arr[N-1] - arr[0].
K must be >0 and <N per constraints, but if K=1, diff = 0 (since max-min = element - itself =0). So min diff = 0. The sliding window works as arr[i] - arr[i] = 0.
So straightforward.
Now the sample: N=5, K=3, arr=1,2,3,4,5 sorted -> windows: [1,2,3] diff=2, [2,3,4] diff=2, [3,4,5] diff=2 => min=2. Output 2.
So answer.
But is there any twist? Possibly we need to consider that array may contain duplicates? That's fine.
Thus final code: read N, K, arr = list of N integers, sort, min_diff = large, for i in range(N-K+1): diff = arr[i+K-1] - arr[i]; min_diff = min(min_diff, diff); print(min_diff).
Complexity O(N log N).
Now we need to respond? The user said: "you are given an array ... Print the minimum difference." This looks like a coding problem; perhaps they expect code.
But the instruction for me: "you are given ..." The user likely wants solution or explanation. They didn't explicitly ask a question, but we should answer with explanation and code.
Given that it's a typical problem, we can provide Python code.
Thus final answer: Explanation and Python code.
Given constraints, use sys.stdin for speed.
Thus I'll produce a response with code and explanation. We need to select K elements from the array to minimize the difference between the maximum and minimum among them. The optimal approach is to sort the array and then consider every contiguous subarray of length K, because the smallest and largest elements in any selected set will be closest if we pick numbers that are near each other after sorting.
After sorting, for each window starting at index i (0 ≤ i ≤ N-K), the difference is arr[i+K-1] - arr[i]. The minimum of these differences is the answer.
Time complexity: O(N log N) for sorting, O(N) for scanning.
Space complexity: O(N) for the array.Here is a Python implementation:
import sys def main(): data = sys.stdin.read().strip().split() if not data: return it = iter(data) N = int(next(it)) K = int(next(it)) arr = [int(next(it)) for _ in range(N)] arr.sort() min_diff = float('inf') for i in range(N - K + 1): diff = arr[i + K - 1] - arr[i] if diff < min_diff: min_diff = diff print(min_diff) if __name__ == "__main__": main()For the sample input:
5 3 1 2 3 4 5The sorted array is [1,2,3,4,5]; the window differences are 2,2,2 → minimum = 2, which matches the sample output.