Given an array of N integers the task is to select K elements out of these N elements in such a way that the minimum difference between each of the K numbers is the Largest. Return the largest minimum difference after choosing any K elements.
Examples:
Input: N = 4, K = 3, arr = [2, 6, 2, 5]
Output: 1
Explanation: 3 elements out of 4 elements are to be selected with a minimum difference as large as possible. Selecting 2, 2, 5 will result in minimum difference as 0. Selecting 2, 5, 6 will result in minimum difference as 6-5=1Input: N = 7, K = 4, arr = [1, 4, 9, 0, 2, 13, 3]
Output: 4
Explanation: Selecting 0, 4, 9, 13 will result in minimum difference of 4, which is the largest minimum difference possible
Naive Approach: Generate all the subsets of size K and find the minimum difference in all of them. Then return the maximum among the differences.
Efficient Approach: Given problem can be solved efficiently using binary search on answer technique. Below steps can be followed to solve the problem:
- Sort the array in ascending order
- Initialize minimum answer ans to 1
- Binary search is used on the range 1 to maximum element in array arr
- Variable dif is used to store the largest minimum difference at every iteration
- Helper function is used to check if selection of K elements is possible with minimum difference greater than dif calculated in previous iteration. If possible then true is returned or else false is returned.
- If above function returns:
- True then update ans to dif and left to dif + 1
- False then update right to dif – 1
Below is the implementation of the above binary search approach
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// To check if selection of K elements// is possible such that difference// between them is greater than difbool isPossibleToSelect(int arr[], int N, int dif, int K){ // Selecting first element in the // sorted array int count = 1; // prev is the previously selected // element initially at index 0 as // first element is already selected int prev = arr[0]; // Check if selection of K-1 elements // from array with a minimum // difference of dif is possible for (int i = 1; i < N; i++) { // If the current element is // atleast dif difference apart // from the previously selected // element then select the current // element and increase the count if (arr[i] >= (prev + dif)) { count++; // If selection of K elements // with a min difference of dif // is possible then return true if (count == K) return true; // Prev will become current // element for the next iteration prev = arr[i]; } } // If selection of K elements with minimum // difference of dif is not possible // then return false return false;}int binarySearch(int arr[], int left, int right, int K, int N){ // Minimum largest difference // possible is 1 int ans = 1; while (left <= right) { int dif = left + (right - left) / 2; // Check if selection of K elements // is possible with a minimum // difference of dif if (isPossibleToSelect(arr, N, dif, K)) { // If dif is greater than // previous ans we update ans ans = max(ans, dif); // Continue to search for better // answer. Try finding greater dif left = dif + 1; } // K elements cannot be selected else right = dif - 1; } return ans;}// Driver codeint main(){ int N, K; N = 7, K = 4; int arr[] = { 1, 4, 9, 0, 2, 13, 3 }; // arr should be in a sorted order sort(arr, arr + N); cout << binarySearch(arr, 0, arr[N - 1], K, N) << "\n"; return 0;} |
Java
// Java implementation for the above approachimport java.io.*;import java.util.Arrays;class GFG{ // To check if selection of K elements // is possible such that difference // between them is greater than dif static boolean isPossibleToSelect(int []arr, int N, int dif, int K) { // Selecting first element in the // sorted array int count = 1; // prev is the previously selected // element initially at index 0 as // first element is already selected int prev = arr[0]; // Check if selection of K-1 elements // from array with a minimum // difference of dif is possible for (int i = 1; i < N; i++) { // If the current element is // atleast dif difference apart // from the previously selected // element then select the current // element and increase the count if (arr[i] >= (prev + dif)) { count++; // If selection of K elements // with a min difference of dif // is possible then return true if (count == K) return true; // Prev will become current // element for the next iteration prev = arr[i]; } } // If selection of K elements with minimum // difference of dif is not possible // then return false return false; } static int binarySearch(int []arr, int left, int right, int K, int N) { // Minimum largest difference // possible is 1 int ans = 1; while (left <= right) { int dif = left + (right - left) / 2; // Check if selection of K elements // is possible with a minimum // difference of dif if (isPossibleToSelect(arr, N, dif, K)) { // If dif is greater than // previous ans we update ans ans = Math.max(ans, dif); // Continue to search for better // answer. Try finding greater dif left = dif + 1; } // K elements cannot be selected else right = dif - 1; } return ans; } // Driver code public static void main(String[] args) { int N, K; N = 7; K = 4; int []arr = { 1, 4, 9, 0, 2, 13, 3 }; // arr should be in a sorted order Arrays.sort(arr); System.out.println(binarySearch(arr, 0, arr[N - 1], K, N)); }}// This code is contributed by shivanisinghss2110 |
Python3
# Python 3 implementation for the above approach# To check if selection of K elements# is possible such that difference# between them is greater than difdef isPossibleToSelect(arr, N, dif, K): # Selecting first element in the # sorted array count = 1 # prev is the previously selected # element initially at index 0 as # first element is already selected prev = arr[0] # Check if selection of K-1 elements # from array with a minimum # difference of dif is possible for i in range(1, N): # If the current element is # atleast dif difference apart # from the previously selected # element then select the current # element and increase the count if (arr[i] >= (prev + dif)): count += 1 # If selection of K elements # with a min difference of dif # is possible then return true if (count == K): return True # Prev will become current # element for the next iteration prev = arr[i] # If selection of K elements with minimum # difference of dif is not possible # then return false return Falsedef binarySearch(arr, left, right, K, N): # Minimum largest difference # possible is 1 ans = 1 while (left <= right): dif = left + (right - left) // 2 # Check if selection of K elements # is possible with a minimum # difference of dif if (isPossibleToSelect(arr, N, dif, K)): # If dif is greater than # previous ans we update ans ans = max(ans, dif) # Continue to search for better # answer. Try finding greater dif left = dif + 1 # K elements cannot be selected else: right = dif - 1 return ans# Driver codeif __name__ == "__main__": N = 7 K = 4 arr = [1, 4, 9, 0, 2, 13, 3] # arr should be in a sorted order arr.sort() print(binarySearch(arr, 0, arr[N - 1], K, N) ) # This code is contributed by ukasp. |
C#
// C# implementation for the above approachusing System;using System.Collections.Generic;class GFG{// To check if selection of K elements// is possible such that difference// between them is greater than difstatic bool isPossibleToSelect(int []arr, int N, int dif, int K){ // Selecting first element in the // sorted array int count = 1; // prev is the previously selected // element initially at index 0 as // first element is already selected int prev = arr[0]; // Check if selection of K-1 elements // from array with a minimum // difference of dif is possible for (int i = 1; i < N; i++) { // If the current element is // atleast dif difference apart // from the previously selected // element then select the current // element and increase the count if (arr[i] >= (prev + dif)) { count++; // If selection of K elements // with a min difference of dif // is possible then return true if (count == K) return true; // Prev will become current // element for the next iteration prev = arr[i]; } } // If selection of K elements with minimum // difference of dif is not possible // then return false return false;}static int binarySearch(int []arr, int left, int right, int K, int N){ // Minimum largest difference // possible is 1 int ans = 1; while (left <= right) { int dif = left + (right - left) / 2; // Check if selection of K elements // is possible with a minimum // difference of dif if (isPossibleToSelect(arr, N, dif, K)) { // If dif is greater than // previous ans we update ans ans = Math.Max(ans, dif); // Continue to search for better // answer. Try finding greater dif left = dif + 1; } // K elements cannot be selected else right = dif - 1; } return ans;}// Driver codepublic static void Main(){ int N, K; N = 7; K = 4; int []arr = { 1, 4, 9, 0, 2, 13, 3 }; // arr should be in a sorted order Array.Sort(arr); Console.Write(binarySearch(arr, 0, arr[N - 1], K, N));}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript Program to implement // the above approach // To check if selection of K elements // is possible such that difference // between them is greater than dif function isPossibleToSelect(arr, N, dif, K) { // Selecting first element in the // sorted array let count = 1; // prev is the previously selected // element initially at index 0 as // first element is already selected let prev = arr[0]; // Check if selection of K-1 elements // from array with a minimum // difference of dif is possible for (let i = 1; i < N; i++) { // If the current element is // atleast dif difference apart // from the previously selected // element then select the current // element and increase the count if (arr[i] >= (prev + dif)) { count++; // If selection of K elements // with a min difference of dif // is possible then return true if (count == K) return true; // Prev will become current // element for the next iteration prev = arr[i]; } } // If selection of K elements with minimum // difference of dif is not possible // then return false return false; } function binarySearch(arr, left, right, K, N) { // Minimum largest difference // possible is 1 let ans = 1; while (left <= right) { let dif = left + Math.floor((right - left) / 2); // Check if selection of K elements // is possible with a minimum // difference of dif if (isPossibleToSelect(arr, N, dif, K)) { // If dif is greater than // previous ans we update ans ans = Math.max(ans, dif); // Continue to search for better // answer. Try finding greater dif left = dif + 1; } // K elements cannot be selected else right = dif - 1; } return ans; } // Driver code let N, K; N = 7, K = 4; let arr = [1, 4, 9, 0, 2, 13, 3]; // arr should be in a sorted order arr.sort(function (a, b) { return a - b }) document.write(binarySearch(arr, 0, arr[N - 1], K, N) + '<br>'); // This code is contributed by Potta Lokesh </script> |
Output
4
Time complexity: O(N * log N)
Space complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
