Dada una array arr[] que consta de N enteros y un entero K , la tarea es encontrar el número mínimo de conjuntos, los elementos de la array se pueden dividir de tal manera que la diferencia entre el elemento máximo y mínimo de cada conjunto sea como máximo K .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}, K = 2
Salida: 2
Explicación:
La array dada se puede dividir en dos conjuntos {1, 2, 3} teniendo la diferencia entre máximo y mínimo como 3 – 1= 2 y {4, 5} teniendo la diferencia entre máximo y mínimo como 5 – 4 = 1.Entrada: arr[] = {5, 2, 9, 7, 3, 2, 4, 6, 14, 10}, K = 3
Salida: 4
Enfoque: el problema dado se puede resolver clasificando la array dada y encontrando el número mínimo de subarreglos . Los elementos de la array se pueden dividir de manera que la diferencia entre el elemento máximo y mínimo sea como máximo K . Siga los pasos a continuación para resolver el problema dado:
- Ordene la array dada arr[] en orden no decreciente .
- Inicialice dos iteradores begin y end como 0 que representan el principio y el final de cada conjunto.
- Inicialice una variable, digamos setCount como 1 que almacene el número mínimo resultante de división de elementos de array en subarreglos.
- Itere un ciclo hasta que el valor de end sea menor que N y realice los siguientes pasos:
- Si el valor de arr[end] – arr[begin] <= K , entonces incremente el valor de end .
- De lo contrario, incremente el valor setCount en 1 y actualice el valor de comienzo a fin que representa el nuevo conjunto.
- Después de completar los pasos anteriores, imprima el valor de setCount como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of sets the array can be divided such
// that for each set max-min <= K
int minSetCount(int arr[], int N, int K)
{
// Sort the input array
sort(arr, arr + N);
// Stores the count of set required
int setCount = 1;
// Stores the beginning and ending
// of the current set
int begin = 0, end = 0;
// Loop to iterate over the array
while (end < N) {
// If arr[end] can be included
// in the current set else
// begin a new set
if (arr[end] - arr[begin] <= K) {
end++;
}
else {
// Increment the set count
setCount++;
begin = end;
}
}
// Return answer
return setCount;
}
// Driver Code
int main()
{
int arr[] = { 5, 2, 9, 7, 3, 2, 4, 6, 14, 10 };
int N = sizeof(arr) / sizeof(int);
int K = 3;
cout << minSetCount(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the minimum number
// of sets the array can be divided such
// that for each set max-min <= K
static int minSetCount(int[] arr, int N, int K)
{
// Sort the input array
Arrays.sort(arr);
// Stores the count of set required
int setCount = 1;
// Stores the beginning and ending
// of the current set
int begin = 0, end = 0;
// Loop to iterate over the array
while (end < N) {
// If arr[end] can be included
// in the current set else
// begin a new set
if (arr[end] - arr[begin] <= K) {
end++;
}
else {
// Increment the set count
setCount++;
begin = end;
}
}
// Return answer
return setCount;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 5, 2, 9, 7, 3, 2, 4, 6, 14, 10 };
int N = arr.length;
int K = 3;
System.out.print(minSetCount(arr, N, K));
}
}
// This code is contributed by subham348.
Python3
# Python 3 program for the above approach # Function to find the minimum number # of sets the array can be divided such # that for each set max-min <= K def minSetCount(arr, N, K): # Sort the input array arr.sort() # Stores the count of set required setCount = 1 # Stores the beginning and ending # of the current set begin = 0 end = 0 # Loop to iterate over the array while (end < N): # If arr[end] can be included # in the current set else # begin a new set if (arr[end] - arr[begin] <= K): end += 1 else: # Increment the set count setCount += 1 begin = end # Return answer return setCount # Driver Code if __name__ == '__main__': arr = [5, 2, 9, 7, 3, 2, 4, 6, 14, 10] N = len(arr) K = 3 print(minSetCount(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the minimum number
// of sets the array can be divided such
// that for each set max-min <= K
static int minSetCount(int[] arr, int N, int K)
{
// Sort the input array
Array.Sort(arr);
// Stores the count of set required
int setCount = 1;
// Stores the beginning and ending
// of the current set
int begin = 0, end = 0;
// Loop to iterate over the array
while (end < N) {
// If arr[end] can be included
// in the current set else
// begin a new set
if (arr[end] - arr[begin] <= K) {
end++;
}
else {
// Increment the set count
setCount++;
begin = end;
}
}
// Return answer
return setCount;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 5, 2, 9, 7, 3, 2, 4, 6, 14, 10 };
int N = arr.Length;
int K = 3;
Console.WriteLine(minSetCount(arr, N, K));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum number
// of sets the array can be divided such
// that for each set max-min <= K
function minSetCount(arr, N, K) {
// Sort the input array
arr.sort(function (a, b) { return a - b })
// Stores the count of set required
let setCount = 1;
// Stores the beginning and ending
// of the current set
let begin = 0, end = 0;
// Loop to iterate over the array
while (end < N) {
// If arr[end] can be included
// in the current set else
// begin a new set
if (arr[end] - arr[begin] <= K) {
end++;
}
else {
// Increment the set count
setCount++;
begin = end;
}
}
// Return answer
return setCount;
}
// Driver Code
let arr = [5, 2, 9, 7, 3, 2, 4, 6, 14, 10];
let N = arr.length;
let K = 3;
document.write(minSetCount(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)