Minimize count of Subsets with difference between maximum and minimum element not exceeding K

0 0 4 minutes read

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 type
int 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 Code
int 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 approach
import java.util.*;
 
class GFG{
 
// Function to find the minimum count 
// of subsets of required type
static 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 Code
public 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 type
def 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 Code
arr = [ 1, 10, 8, 3, 9 ]
K = 3
N = len(arr)
 
# Function call
print(findCount(arr, N, K))
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// above approach
using System;
class GFG{
 
// Function to find the minimum count 
// of subsets of required type
static 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 Code
public 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 type
function 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:

Time Complexity: O(NLog(N))
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!