Minimice los elementos consecutivos que se agregarán para cada elemento para hacer una array de al menos C longitud

Dada una array ordenada arr[] de tamaño N , donde arr[i] denota la posición inicial de una secuencia, la tarea es encontrar el número mínimo de elementos consecutivos (por ejemplo, K ) que se pueden agregar para cada elemento de la array para hacer el Longitud de la array al menos C .

Nota: Los números consecutivos se pueden sumar hasta un mínimo de arr[i]+K o (arr[i+1]-1) .

Ejemplos:

Entrada: arr[] = { 1, 2, 4, 5, 7}, C = 3 Salida
: 1 Explicación
: Para K = 1, son posibles 5 números (uno de cada posición).
Desde la posición 1, seleccione ‘1’.
Desde la posición 2: seleccione ‘2’
Desde la posición 4: seleccione ‘4’
Desde la posición 5: seleccione ‘5’
Desde la posición 7: seleccione ‘7’
Elementos totales de la secuencia = 5, que es mayor que 3

Entrada: arr [] = {2, 4, 10}, C = 10
Salida: 4
Explicación: Las  secuencias dadas son: { 2 , 3}, { 4 , 5, 6, 7, 8, 9}, { 10, 11 , 12, 13, 14 . . . }
Elementos seleccionados = { 2, 3, 4, 5, 6, 7, 10, 11, 12, 13}
El valor mínimo debe ser 4.
Desde la posición 2 -> 2, 3 porque 
la siguiente secuencia comienza en 4, por lo que 4 elementos no pueden ser seleccionado de esta secuencia
Desde la posición 4 – 4, 5, 6, 7
Desde la posición 10 – 10, 11, 12, 13
Elementos totales de la secuencia = 10 { 2, 3, 4, 5, 6, 7, 10, 11, 12, 13}.

Enfoque ingenuo: la idea básica para resolver el problema es simplemente atravesar la array .

Siga los pasos que se mencionan a continuación:

• Comience tomando K = 1, y para cada K verifique si es posible obtener C elementos de las secuencias.
• Si es posible, entonces K es la respuesta; de lo contrario, incremente K en 1 y continúe hasta que se cumpla la condición.

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

Enfoque Eficiente: El problema se puede resolver en base a la siguiente idea:

Utilice la búsqueda binaria en K . Si para cualquier valor de K es posible encontrar elementos C en la secuencia, intente con un valor más bajo en la mitad inferior. De lo contrario, intente con un valor más alto de K en la mitad superior.

Siga los pasos para resolver el problema:

• Intente encontrar el valor de K en el rango de 1 a C utilizando la búsqueda binaria configurando bajo = 1 y alto = C ;
  • Si se recopilaron al menos C elementos, verifique en la mitad izquierda para encontrar el valor mínimo de K .
  • De lo contrario, verifique en la mitad superior (es decir, para valores mayores que el valor medio).
• Una vez completada la búsqueda, devuelva low , que representará el mínimo K .

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

// C++ code to implement the above approach.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the min value of K
void solver(vector<int> arr, int C)
{
  int low = 1;
  int high = C;
  int mid = 0;
  int sum = 0;
  int n = arr.size();
 
  // Binary search to find min of K
  while (low < high) {
    mid = (low + high) / 2;
    sum = mid;
    for (int k = 1; k < n; k++) {
 
      sum += min(mid, arr[k] - arr[k - 1]);
    }
 
    // If atleast C numbers are found,
    // then search in left side
    // to get minimum value of k
    if (sum >= C) {
      high = mid;
    }
    else {
      // If we are not able to get
      // atleast C elements,
      // then move in
      // right direction
      low = mid + 1;
    }
  }
  cout << low << endl;
}
 
// Driver code
int main()
{
  vector<int> arr = { 2, 4, 10 };
  int C = 10;
  solver(arr, C);
}
 
// This code is contributed by Taranpreet

// Java code to implement the above approach.
 
import java.io.*;
 
class GFG {
 
    // Function to find the min value of K
    public static void solver(int[] arr, int C)
    {
        int low = 1;
        int high = C;
        int mid = 0;
        int sum = 0;
        int n = arr.length;
 
        // Binary search to find min of K
        while (low < high) {
            mid = (low + high) / 2;
            sum = mid;
            for (int k = 1; k < n; k++) {
 
                sum
                    += Math.min(mid,
                                arr[k] - arr[k - 1]);
            }
 
            // If atleast C numbers are found,
            // then search in left side
            // to get minimum value of k
            if (sum >= C) {
                high = mid;
            }
            else {
                // If we are not able to get
                // atleast C elements,
                // then move in
                // right direction
                low = mid + 1;
            }
        }
        System.out.println(low);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 2, 4, 10 };
        int C = 10;
        solver(arr, C);
    }
}

# Python code for the above approach
 
# Function to find the min value of K
def solver(arr, C):
    low = 1
    high = C
    mid = 0
    sum = 0
    n = len(arr)
 
    # Binary search to find min of K
    while (low < high):
        mid = (low + high) // 2
        sum = mid
        for k in range(1,n):
 
            sum += min(mid,arr[k] - arr[k - 1])
  
 
        # If atleast C numbers are found,
        # then search in left side
        # to get minimum value of k
        if (sum >= C):
            high = mid
        else:
            # If we are not able to get
            # atleast C elements,
            # then move in
            # right direction
            low = mid + 1
    print(low)
 
# Driver code
arr = [2, 4, 10]
C = 10
solver(arr, C)
 
# This code is contributed byshinjanpatra

// C# code to implement the above approach.
using System;
 
class GFG {
 
  // Function to find the min value of K
  static void solver(int[] arr, int C)
  {
    int low = 1;
    int high = C;
    int mid = 0;
    int sum = 0;
    int n = arr.Length;
 
    // Binary search to find min of K
    while (low < high) {
      mid = (low + high) / 2;
      sum = mid;
      for (int k = 1; k < n; k++) {
 
        sum
          += Math.Min(mid,
                      arr[k] - arr[k - 1]);
      }
 
      // If atleast C numbers are found,
      // then search in left side
      // to get minimum value of k
      if (sum >= C) {
        high = mid;
      }
      else {
        // If we are not able to get
        // atleast C elements,
        // then move in
        // right direction
        low = mid + 1;
      }
    }
    Console.WriteLine(low);
  }
 
  // Driver code
  public static void Main()
  {
    int []arr = { 2, 4, 10 };
    int C = 10;
    solver(arr, C);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
        // JavaScript code for the above approach
 
        // Function to find the min value of K
        function solver(arr, C) {
            let low = 1;
            let high = C;
            let mid = 0;
            let sum = 0;
            let n = arr.length;
 
            // Binary search to find min of K
            while (low < high) {
                mid = Math.floor((low + high) / 2);
                sum = mid;
                for (let k = 1; k < n; k++) {
 
                    sum
                        += Math.min(mid,
                            arr[k] - arr[k - 1]);
                }
 
                // If atleast C numbers are found,
                // then search in left side
                // to get minimum value of k
                if (sum >= C) {
                    high = mid;
                }
                else {
                    // If we are not able to get
                    // atleast C elements,
                    // then move in
                    // right direction
                    low = mid + 1;
                }
            }
            document.write(low);
        }
 
        // Driver code
        let arr = [2, 4, 10];
        let C = 10;
        solver(arr, C);
 
     // This code is contributed by Potta Lokesh
    </script>

4

Complejidad de tiempo: O(N * log C)
Espacio auxiliar: O(1)