Número mínimo de inserciones requeridas de modo que los primeros K números naturales se puedan obtener como suma de una subsecuencia de la array

Dada una array arr[] que consta de N enteros positivos y un entero positivo K , la tarea es encontrar el número mínimo de elementos que se requiere insertar de modo que todos los números del rango [1, K] se puedan obtener como el suma de cualquier subsecuencia de la array.

Ejemplos:

Entrada: arr[] = {1, 3, 5}, K = 10
Salida: 1
Explicación:
Agregar el elemento {1} a la array modifica la array a {1, 3, 5, 1}. Ahora toda la suma sobre el rango [1, K] se puede obtener como:

1. Suma 1: Los elementos son {1}.
2. Suma 2: Los elementos son {1, 1}.
3. Suma 3: Los elementos son {3}.
4. Suma 4: Los elementos son {1. 3}.
5. Suma 5: Los elementos son {1, 3, 1}.
6. Suma 6: Los elementos son {1, 5}.
7. Suma 7: Los elementos son {1, 5, 1}.
8. Suma 8: Los elementos son {3, 5}.
9. Suma 9: Los elementos son {1, 3, 5}.
10. Suma 10: Los elementos son {1, 3, 5, 1}.

Entrada: arr[] = {2, 6, 8, 12, 19}, K = 20
Salida: 2

Enfoque: el problema dado se puede resolver clasificando la array en orden creciente y luego tratando de hacer que el valor de la suma esté en el rango [1, K] usando el hecho de que si la suma de los elementos de la array X , entonces todos los valores en el rango Se puede formar [1, X] . De lo contrario, se requiere insertar el valor (suma + 1) como un elemento de array. Siga los pasos a continuación para resolver el problema:

• Ordene la array arr[] en orden creciente .
• Inicialice la variable, diga índice como 0 para mantener el índice del elemento de array y cuente como 0 para almacenar los elementos totales resultantes agregados.
• Si el valor de arr[0] es mayor que 1 , entonces se debe agregar 1, por lo tanto, aumente el valor de la cuenta en 1 . De lo contrario, aumente el valor del índice en 1 .
• Inicialice la variable, digamos esperar como 2 para mantener el siguiente valor esperado en el rango de 1 a K que se formará a partir de la array arr[] .
• Iterar un bucle hasta que el valor de expect sea como máximo K y realizar los siguientes pasos:
  • Si el índice es mayor que igual a N o arr[índice] es mayor que el valor de expect , aumente el valor de count por 1 y multiplique el valor de expect por 2.
  • De lo contrario, aumente el valor de expect por arr[index] y aumente el valor del índice por 1 .
• Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number of elements that must
// be added to make the sum of array element over the range
// [1, K]
void findMinimumNumberOfElements(int n, int k, int arr[])
{
    // Sort the given array
    sort(arr, arr + n);
 
    // Stores the index for the array
    int index = 0, count = 0;
    // If 1 is not present, then append it
    if (arr[0] > 1)
        ++count;
    // Move on to next index
    else
        ++index;
 
    // The expected value in the array
    long long expect = 2;
    while (expect <= k) {
        // Need to append this number
        if (index >= n || arr[index] > expect) {
            ++count;
            expect += expect;
        }
 
        // Otherwise, expand the range by current number
        else {
            expect += arr[index];
            ++index;
        }
    }
    // Print the answer
    cout << count;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 6, 8, 12, 19 };
    int K = 20;
    int N = sizeof(arr) / sizeof(arr[0]);
    findMinimumNumberOfElements(N, K, arr);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// C program for the above approach
 
#include <stdio.h>
#include <stdlib.h>
 
int cmpfunc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}
 
// Function to find the minimum number of elements that must
// be added to make the sum of array element over the range
// [1, K]
void findMinimumNumberOfElements(int n, int k, int arr[])
{
    // Sort the given array
    qsort(arr, n, sizeof(int), cmpfunc);
 
    // Stores the index for the array
    int index = 0, count = 0;
    // If 1 is not present, then append it
    if (arr[0] > 1)
        ++count;
    // Move on to next index
    else
        ++index;
 
    // The expected value in the array
    long long expect = 2;
    while (expect <= k) {
        // Need to append this number
        if (index >= n || arr[index] > expect) {
            ++count;
            expect += expect;
        }
 
        // Otherwise, expand the range by current number
        else {
            expect += arr[index];
            ++index;
        }
    }
    // Print the answer
    printf("%d", count);
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 6, 8, 12, 19 };
    int K = 20;
    int N = sizeof(arr) / sizeof(arr[0]);
    findMinimumNumberOfElements(N, K, arr);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
 
class GFG {
 
    // Function to find the minimum number of elements that
    // must be added to make the sum of array element over
    // the range [1, K]
    static void findMinimumNumberOfElements(int n, int k, int[] arr)
    {
        // Sort the given array
        Arrays.sort(arr);
 
        // Stores the index for the array
        int index = 0, count = 0;
        // If 1 is not present, then append it
 
        if (arr[0] > 1)
            ++count;
        // Move on to next index
        else
            ++index;
 
        // The expected value in the array
        long expect = 2;
        while (expect <= k) {
 
            // Need to append this number
            if (index >= n || arr[index] > expect) {
                ++count;
                expect += expect;
            }
 
            // Otherwise, expand the range by current number
            else {
                expect += arr[index];
                ++index;
            }
        }
 
        // Print the answer
        System.out.println(count);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 2, 6, 8, 12, 19 };
        int K = 20;
        int N = arr.length;
        findMinimumNumberOfElements(N, K, arr);
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

# Python 3 program for the above approach
 
# Function to find the minimum number
# of elements that must be added to
# make the sum of array element over
# the range [1, K]
def findMinimumNumberOfElements(n, k, arr):
    # Sort the given array
    arr.sort()
 
    # Stores the index for the
    # array
    index = 0
    count = 0
 
    if (arr[0] > 1):
        # If 1 is not present, then
        # append it
        count += 1
 
    # Move on to next index
    else:
        index += 1
 
    # The expected value in the array
    expect = 2
    while (expect <= k):
 
        # Need to append this number
        if (index >= n or arr[index] > expect):
            count += 1
            expect += expect
 
        # Otherwise, expand the range
        # by current number
        else:
            expect += arr[index]
            index += 1
 
    # Print the answer
    print(count)
 
# Driver Code
if __name__ == '__main__':
    arr = [2, 6, 8, 12, 19]
    K = 20
    N = len(arr)
    findMinimumNumberOfElements(N, K, arr)
     
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
 
class GFG {
     
 // Function to find the minimum number
    // of elements that must be added to
    // make the sum of array element over
    // the range [1, K]
    static void findMinimumNumberOfElements(int n, int k,
                                            int[] arr)
    {
        // Sort the given array
        Array.Sort(arr);
 
        // Stores the index for the
        // array
        int index = 0;
        int count = 0;
 
        if (arr[0] > 1) {
 
            // If 1 is not present, then
            // append it
            ++count;
        }
 
        // Move on to next index
        else {
            ++index;
        }
 
        // The expected value in the array
        long expect = 2;
        while (expect <= k) {
 
            // Need to append this number
            if (index >= n || arr[index] > expect) {
                ++count;
                expect += expect;
            }
 
            // Otherwise, expand the range
            // by current number
            else {
                expect += arr[index];
                ++index;
            }
        }
 
        // Print the answer
        Console.WriteLine(count);
    }
     
    // Driver code
    public static void Main()
    {
        int[] arr = { 2, 6, 8, 12, 19 };
        int K = 20;
        int N = arr.Length;
        findMinimumNumberOfElements(N, K, arr);
    }
}
 
// This code is contributed by avijitmondal1998.

<script>
// Javascript program for the above approach
 
// Function to find the minimum number
// of elements that must be added to
// make the sum of array element over
// the range [1, K]
function findMinimumNumberOfElements(n, k, arr) {
    // Sort the given array
    arr.sort((a, b) => a - b);
 
    // Stores the index for the
    // array
    let index = 0;
    let count = 0;
 
    if (arr[0] > 1) {
 
        // If 1 is not present, then
        // append it
        ++count;
    }
 
    // Move on to next index
    else {
        ++index;
    }
 
    // The expected value in the array
    let expect = 2;
    while (expect <= k) {
 
        // Need to append this number
        if (index >= n || arr[index] > expect) {
            ++count;
            expect += expect;
        }
 
        // Otherwise, expand the range
        // by current number
        else {
            expect += arr[index];
            ++index;
        }
    }
 
    // Print the answer
    document.write(count);
}
 
// Driver Code
 
let arr = [2, 6, 8, 12, 19];
let K = 20;
let N = arr.length;
findMinimumNumberOfElements(N, K, arr);
 
// This code is contributed by _saurabh_jaiswal.
</script>

2

Complejidad de tiempo: O(max(K, N*log N))
Espacio auxiliar: O(1)