Minimize count of Subsets with difference between maximum and minimum element not exceeding K
Given an array arr[ ] and an integer K, the task is to split the given array into minimum number of subsets having the difference between the maximum and the minimum element ≤ K.
Examples:
Input: arr[ ] = {1, 3, 7, 9, 10}, K = 3
Output: 2
Explanation:
One of the possible subsets of arr[] are {1, 3} and {7, 9, 10} where the difference between maximum and minimum element does not greater than K i.e, 3.Input: arr[ ] = {1, 10, 8, 3, 9}, K =3
Output: 2.
Approach: Follow the steps below to solve the problem:
- Sort the array in ascending order.
- Iterate over the array, setting currMin as the first element of the array and keep updating currMax with the elements traversed.
- If at any index, the difference between currMax and currMin exceeds K, increment answer by 1 and set currMax and currMin to arr[i].
- Finally, return answer.
Below is the implementation of the above approach:
C++
// C++ Program to implement// above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum count // of subsets of required typeint findCount(int arr[], int N, int K){ sort(arr, arr + N); // Stores the result int result = 1; // Store the maximum and minimum // element of the current subset int cur_max = arr[0]; int cur_min = arr[0]; for (int i = 1; i < N; i++) { // Update current maximum cur_max = arr[i]; // If difference exceeds K if (cur_max - cur_min > K) { // Update count result++; // Update maximum and minimum // to the current subset cur_max = arr[i]; cur_min = arr[i]; } } return result;}// Driver Codeint main(){ int arr[] = { 1,10, 8, 3, 9 }; int K = 3; int N = sizeof(arr) / sizeof(arr[0]); cout << findCount(arr, N, K); return 0;} |
Java
// Java program to implement// above approachimport java.util.*;class GFG{// Function to find the minimum count // of subsets of required typestatic int findCount(int arr[], int N, int K){ Arrays.sort(arr); // Stores the result int result = 1; // Store the maximum and minimum // element of the current subset int cur_max = arr[0]; int cur_min = arr[0]; for(int i = 1; i < N; i++) { // Update current maximum cur_max = arr[i]; // If difference exceeds K if (cur_max - cur_min > K) { // Update count result++; // Update maximum and minimum // to the current subset cur_max = arr[i]; cur_min = arr[i]; } } return result;}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 10, 8, 3, 9 }; int K = 3; int N = arr.length; System.out.print(findCount(arr, N, K));}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program to implement# the above approach# Function to find the minimum count# of subsets of required typedef findCount(arr, N, K): arr.sort() # Stores the result result = 1 # Store the maximum and minimum # element of the current subset cur_max = arr[0] cur_min = arr[0] for i in range(1, N): # Update current maximum cur_max = arr[i] # If difference exceeds K if(cur_max - cur_min > K): # Update count result += 1 # Update maximum and minimum # to the current subset cur_max = arr[i] cur_min = arr[i] return result# Driver Codearr = [ 1, 10, 8, 3, 9 ]K = 3N = len(arr)# Function callprint(findCount(arr, N, K))# This code is contributed by Shivam Singh |
C#
// C# program to implement// above approachusing System;class GFG{// Function to find the minimum count // of subsets of required typestatic int findCount(int []arr, int N, int K){ Array.Sort(arr); // Stores the result int result = 1; // Store the maximum and minimum // element of the current subset int cur_max = arr[0]; int cur_min = arr[0]; for(int i = 1; i < N; i++) { // Update current maximum cur_max = arr[i]; // If difference exceeds K if (cur_max - cur_min > K) { // Update count result++; // Update maximum and minimum // to the current subset cur_max = arr[i]; cur_min = arr[i]; } } return result;}// Driver Codepublic static void Main(String[] args){ int []arr = { 1, 10, 8, 3, 9 }; int K = 3; int N = arr.Length; Console.Write(findCount(arr, N, K));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program for the// above approach// Function to find the minimum count// of subsets of required typefunction findCount(arr, N, K){ arr.sort(); // Stores the result let result = 1; // Store the maximum and minimum // element of the current subset let cur_max = arr[0]; let cur_min = arr[0]; for(let i = 1; i < N; i++) { // Update current maximum cur_max = arr[i]; // If difference exceeds K if (cur_max - cur_min > K) { // Update count result++; // Update maximum and minimum // to the current subset cur_max = arr[i]; cur_min = arr[i]; } } return result;} // Driver Code let arr = [ 1, 10, 8, 3, 9 ]; let K = 3; let N = arr.length; document.write(findCount(arr, N, K)); // This code is contributed by target_2.</script> |
Output:
2
Time Complexity: O(NLog(N))
Auxiliary Space: 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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
