Minimice las divisiones en un Array dado para encontrar subconjuntos de como máximo 2 elementos con suma como máximo K

Dada una array arr[] de N enteros y un entero K , la tarea es calcular el número mínimo de subconjuntos de casi 2 elementos, la array se puede dividir de manera que la suma de los elementos en cada subconjunto sea casi  K.

Ejemplos:

Entrada: arr[] = {1, 2, 3}, K = 3
Salida: 2
Explicación: La array dada se puede dividir en subconjuntos como {1, 2} y {3}, y la suma de ambos subconjuntos es como máximo K. Por lo tanto, el número de subconjuntos es 2, que es el mínimo posible.

Entrada: arr[] = {3, 2, 2, 3, 1}, K = 3
Salida: 4

Entrada: arr[] = {3, 2, 2, 3, 1}, K = 2
Salida: -1

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso con la ayuda del enfoque de dos punteros . La idea es agrupar el entero con valor mínimo con el valor máximo posible de modo que su suma no exceda K . Siga los pasos para resolver el problema dado:

• Ordena la array dada en orden no decreciente.
• Cree dos variables, i = 0 y j = N – 1 , donde i representa el primer índice y j representa el último índice de la array.
• Si la suma de arr[i] y arr[j] es casi K , incremente i y disminuya j. Además, incremente el recuento de subconjuntos en 1 .
• Si la suma de arr[i] y arr[j] es mayor que K , disminuya j e incremente el conteo de subconjuntos.

A continuación se muestra la implementación del enfoque anterior:

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to split array into minimum
// subsets of at most 2 elements with
// sum of each subset at most K
int minSubsetCnt(vector<int>& arr, int K)
{
    // Sort arr in increasing order
    sort(arr.begin(), arr.end());
 
    // If it is impossible
    if (arr[arr.size() - 1] > K) {
        return -1;
    }
 
    // Stores the count of subsets
    int cnt = 0;
 
    // Starting pointer
    int i = 0;
 
    // End pointer
    int j = arr.size() - 1;
 
    // Loop for the two
    // pointer approach
    while (i <= j) {
        if (arr[i] + arr[j] <= K) {
            cnt++;
            i++;
            j--;
        }
        else {
            cnt++;
            j--;
        }
    }
 
    // Return Answer
    return cnt;
}
// Driver Code
int main()
{
    vector<int> arr{ 3, 2, 2, 3, 1 };
    int K = 3;
    cout << minSubsetCnt(arr, K);
 
    return 0;
}

// Java program of the above approach
import java.util.*;
 
class GFG{
 
// Function to split array into minimum
// subsets of at most 2 elements with
// sum of each subset at most K
static int minSubsetCnt(int[] arr, int K)
{
     
    // Sort arr in increasing order
    Arrays.sort(arr);
 
    // If it is impossible
    if (arr[arr.length - 1] > K)
    {
        return -1;
    }
 
    // Stores the count of subsets
    int cnt = 0;
 
    // Starting pointer
    int i = 0;
 
    // End pointer
    int j = arr.length - 1;
 
    // Loop for the two
    // pointer approach
    while (i <= j)
    {
        if (arr[i] + arr[j] <= K)
        {
            cnt++;
            i++;
            j--;
        }
        else
        {
            cnt++;
            j--;
        }
    }
 
    // Return Answer
    return cnt;
}
 
// Driver Code
public static void main(String args[])
{
    int[] arr = { 3, 2, 2, 3, 1 };
    int K = 3;
     
    System.out.print(minSubsetCnt(arr, K));
}
}
 
// This code is contributed by sanjoy_62

# Python program of the above approach
 
# Function to split array into minimum
# subsets of at most 2 elements with
# sum of each subset at most K
def minSubsetCnt(arr, K):
     
    # Sort arr in increasing order
    arr.sort()
 
    # If it is impossible
    if (arr[len(arr) - 1] > K):
        return -1
 
    # Stores the count of subsets
    cnt = 0;
 
    # Starting pointer
    i = 0;
 
    # End pointer
    j = len(arr) - 1;
 
    # Loop for the two
    # pointer approach
    while (i <= j):
        if (arr[i] + arr[j] <= K):
            cnt = cnt + 1
            i = i + 1
            j = j - 1
             
        else:
            cnt = cnt + 1
            j = j - 1
 
    # Return Answer
    return cnt
 
# Driver Code
arr = [ 3, 2, 2, 3, 1 ]
K = 3
print(minSubsetCnt(arr, K))
 
# This code is contributed by Samim Hossain Mondal.

// C# implementation for the above approach
using System;
class GFG
{
   
// Function to split array into minimum
// subsets of at most 2 elements with
// sum of each subset at most K
static int minSubsetCnt(int[] arr, int K)
{
     
    // Sort arr in increasing order
    Array.Sort(arr);
 
    // If it is impossible
    if (arr[arr.Length - 1] > K)
    {
        return -1;
    }
 
    // Stores the count of subsets
    int cnt = 0;
 
    // Starting pointer
    int i = 0;
 
    // End pointer
    int j = arr.Length - 1;
 
    // Loop for the two
    // pointer approach
    while (i <= j)
    {
        if (arr[i] + arr[j] <= K)
        {
            cnt++;
            i++;
            j--;
        }
        else
        {
            cnt++;
            j--;
        }
    }
 
    // Return Answer
    return cnt;
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 3, 2, 2, 3, 1 };
    int K = 3;
     
    Console.Write(minSubsetCnt(arr, K));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to split array into minimum
       // subsets of at most 2 elements with
       // sum of each subset at most K
       function minSubsetCnt(arr, K) {
           // Sort arr in increasing order
           arr.sort(function (a, b) { return a - b })
 
           // If it is impossible
           if (arr[arr.length - 1] > K) {
               return -1;
           }
 
           // Stores the count of subsets
           let cnt = 0;
 
           // Starting pointer
           let i = 0;
 
           // End pointer
           let j = arr.length - 1;
 
           // Loop for the two
           // pointer approach
           while (i <= j) {
               if (arr[i] + arr[j] <= K) {
                   cnt++;
                   i++;
                   j--;
               }
               else {
                   cnt++;
                   j--;
               }
           }
 
           // Return Answer
           return cnt;
       }
       // Driver Code
 
       let arr = [3, 2, 2, 3, 1];
       let K = 3;
       document.write(minSubsetCnt(arr, K));
 
 // This code is contributed by Potta Lokesh
   </script>

4

Complejidad temporal: O(N*log N)
Espacio auxiliar: O(1)