Número mínimo de calcetines requeridos para tener al menos K pares del mismo color

Dada una array arr[] que consta de N enteros tales que arr[i] representa el número de calcetines del color i y un entero K , la tarea es encontrar el número mínimo de calcetines necesarios para obtener al menos K pares de calcetines del mismo color.

Ejemplos:

Entrada: arr[] = {3, 4, 5, 3}, K = 6
Salida: 15
Explicación: Uno tendrá que recoger todos los calcetines para obtener al menos 6 pares de calcetines iguales.

Entrada: arr[] = {4, 5, 6}, K = 3
Salida: 8

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones: 

• De acuerdo con el principio de Pigeonhole, es decir, en el peor de los casos, si se han elegido N calcetines de diferentes colores, la siguiente elección formará un par de calcetines iguales.
• Supongamos que uno ha elegido N calcetines de diferentes colores, entonces, para cada (K – 1) pares, tendrá que elegir dos calcetines, uno para formar un par y otro para mantener N calcetines de todos los colores diferentes, y para el último par, hay Solo es necesario elegir un solo calcetín de cualquier color disponible.

Por lo tanto, la idea es encontrar el número total de pares que se pueden formar con los mismos colores y si el conteo total es como máximo K , imprima (2*K + N – 1) como el conteo mínimo de pares a elegir. De lo contrario, escriba «-1» ya que no hay suficientes calcetines para formar K pares.

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

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to count the minimum
// number of socks to be picked
int findMin(int arr[], int N, int k)
{
    // Stores the total count
    // of pairs of socks
    int pairs = 0;
 
    // Find the total count of pairs
    for (int i = 0; i < N; i++) {
        pairs += arr[i] / 2;
    }
 
    // If K is greater than pairs
    if (k > pairs)
        return -1;
 
    // Otherwise
    else
        return 2 * k + N - 1;
}
 
int main()
{
    int arr[3] = { 4, 5, 6 };
    int K = 3;
    cout << findMin(arr, 3, K);
    return 0;
}
 
// This code is contributed by RohitOberoi.

// Java program for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to count the minimum
    // number of socks to be picked
    public static int findMin(
        int[] arr, int N, int k)
    {
        // Stores the total count
        // of pairs of socks
        int pairs = 0;
 
        // Find the total count of pairs
        for (int i = 0; i < N; i++) {
            pairs += arr[i] / 2;
        }
 
        // If K is greater than pairs
        if (k > pairs)
            return -1;
 
        // Otherwise
        else
            return 2 * k + N - 1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 4, 5, 6 };
        int K = 3;
        int N = arr.length;
        System.out.println(findMin(arr, N, K));
    }
}

// C# program for the above approach
 
using System;
 
class GFG {
 
    // Function to count the minimum
    // number of socks to be picked
    public static int findMin(int[] arr, int N, int k)
    {
        // Stores the total count
        // of pairs of socks
        int pairs = 0;
 
        // Find the total count of pairs
        for (int i = 0; i < N; i++) {
            pairs += arr[i] / 2;
        }
 
        // If K is greater than pairs
        if (k > pairs)
            return -1;
 
        // Otherwise
        else
            return 2 * k + N - 1;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { 4, 5, 6 };
        int K = 3;
        int N = arr.Length;
        Console.WriteLine(findMin(arr, N, K));
    }
}
 
// This code is contributed by ukasp.

# Python program for the above approach
 
# Function to count the minimum
# number of socks to be picked
def findMin(arr, N, k):
   
    # Stores the total count
    # of pairs of socks
    pairs = 0
     
    # Find the total count of pairs
    for i in range(N):
        pairs += arr[i] / 2
     
    # If K is greater than pairs
    if (k > pairs):
        return -1
 
    # Otherwise
    else:
        return 2 * k + N - 1
         
arr = [4, 5, 6]
k = 3
print(findMin(arr, 3, k));
     
# This code is contributed by SoumikMondal.

<script>
 
// JavaScript program to implement
// the above approach
 
    // Function to count the minimum
    // number of socks to be picked
    function findMin(
        arr, N, k)
    {
        // Stores the total count
        // of pairs of socks
        let pairs = 0;
  
        // Find the total count of pairs
        for (let i = 0; i < N; i++) {
            pairs += arr[i] / 2;
        }
  
        // If K is greater than pairs
        if (k > pairs)
            return -1;
  
        // Otherwise
        else
            return 2 * k + N - 1;
    }
 
// Driver code
 
        let arr = [ 4, 5, 6 ];
        let K = 3;
        let N = arr.length;
        document.write(findMin(arr, N, K));
            
</script>

8

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