Dada una array arr[] de N elementos y un entero S . La tarea es encontrar el número mínimo K tal que la suma de los elementos del arreglo no exceda S después de dividir todos los elementos por K .
Nota: considere la división de enteros.
Ejemplos:
Entrada: arr[] = {10, 7, 8, 10, 12, 19}, S = 27
Salida: 3
Después de dividir por 3, la array se convierte en
{3, 2, 2, 3, 4, 6} y la nueva la suma es 20.
Entrada: arr[] = {19, 17, 11, 10}, S = 40
Salida: 2
Enfoque ingenuo: iterar para todos los valores de K desde 1 hasta el elemento máximo en la array más un elemento no máximo porque si ponemos k como elemento máximo, la suma será uno y qué pasa si la S se nos da como cero. Entonces iteramos desde k = 1 hasta el elemento máximo en la array más uno. y luego sumar los elementos de la array dividiendo con K , si la suma no excede S , entonces el valor actual será la respuesta. La complejidad temporal de este enfoque será O(M * N) donde M es el elemento máximo de la array.
Enfoque eficiente: un enfoque eficiente es encontrar el valor de K realizando una búsqueda binariaen la respuesta Inicie una búsqueda binaria en el valor de K y se realiza una verificación dentro para ver si la suma excede K , luego la búsqueda binaria se realiza en la segunda mitad o la primera mitad según corresponda.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum value of k
// that satisfies the given condition
int findMinimumK(int a[], int n, int s)
{
// Find the maximum element
int maximum = a[0];
for (int i = 0; i < n; i++) {
maximum = max(maximum, a[i]);
}
// Lowest answer can be 1 and the
// highest answer can be (maximum + 1)
int low = 1, high = maximum + 1;
int ans = high;
// Binary search
while (low <= high) {
// Get the mid element
int mid = (low + high) / 2;
int sum = 0;
// Calculate the sum after dividing
// the array by new K which is mid
for (int i = 0; i < n; i++) {
sum += (int)(a[i] / mid);
}
// Search in the second half
if (sum > s)
low = mid + 1;
// First half
else {
ans = min(ans, mid);
high = mid - 1;
}
}
return ans;
}
// Driver code
int main()
{
int a[] = { 10, 7, 8, 10, 12, 19 };
int n = sizeof(a) / sizeof(a[0]);
int s = 27;
cout << findMinimumK(a, n, s);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the minimum value of k
// that satisfies the given condition
static int findMinimumK(int a[],
int n, int s)
{
// Find the maximum element
int maximum = a[0];
for (int i = 0; i < n; i++)
{
maximum = Math.max(maximum, a[i]);
}
// Lowest answer can be 1 and the
// highest answer can be (maximum + 1)
int low = 1, high = maximum + 1;
int ans = high;
// Binary search
while (low <= high)
{
// Get the mid element
int mid = (low + high) / 2;
int sum = 0;
// Calculate the sum after dividing
// the array by new K which is mid
for (int i = 0; i < n; i++)
{
sum += (int)(a[i] / mid);
}
// Search in the second half
if (sum > s)
low = mid + 1;
// First half
else
{
ans = Math.min(ans, mid);
high = mid - 1;
}
}
return ans;
}
// Driver code
public static void main (String[] args)
{
int a[] = { 10, 7, 8, 10, 12, 19 };
int n = a.length;
int s = 27;
System.out.println(findMinimumK(a, n, s));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the minimum value of k # that satisfies the given condition def findMinimumK(a, n, s): # Find the maximum element maximum = a[0] for i in range(n): maximum = max(maximum, a[i]) # Lowest answer can be 1 and the # highest answer can be (maximum + 1) low = 1 high = maximum + 1 ans = high # Binary search while (low <= high): # Get the mid element mid = (low + high) // 2 sum = 0 # Calculate the sum after dividing # the array by new K which is mid for i in range(n): sum += (a[i] // mid) # Search in the second half if (sum > s): low = mid + 1 # First half else: ans = min(ans, mid) high = mid - 1 return ans # Driver code a = [10, 7, 8, 10, 12, 19] n = len(a) s = 27 print(findMinimumK(a, n, s)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the minimum value of k
// that satisfies the given condition
static int findMinimumK(int []a,
int n, int s)
{
// Find the maximum element
int maximum = a[0];
for (int i = 0; i < n; i++)
{
maximum = Math.Max(maximum, a[i]);
}
// Lowest answer can be 1 and the
// highest answer can be (maximum + 1)
int low = 1, high = maximum + 1;
int ans = high;
// Binary search
while (low <= high)
{
// Get the mid element
int mid = (low + high) / 2;
int sum = 0;
// Calculate the sum after dividing
// the array by new K which is mid
for (int i = 0; i < n; i++)
{
sum += (int)(a[i] / mid);
}
// Search in the second half
if (sum > s)
low = mid + 1;
// First half
else
{
ans = Math.Min(ans, mid);
high = mid - 1;
}
}
return ans;
}
// Driver code
public static void Main ()
{
int []a = { 10, 7, 8, 10, 12, 19 };
int n = a.Length;
int s = 27;
Console.WriteLine(findMinimumK(a, n, s));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Function to return the minimum value of k
// that satisfies the given condition
function findMinimumK(a , n , s) {
// Find the maximum element
var maximum = a[0];
for (i = 0; i < n; i++) {
maximum = Math.max(maximum, a[i]);
}
// Lowest answer can be 1 and the
// highest answer can be (maximum + 1)
var low = 1, high = maximum + 1;
var ans = high;
// Binary search
while (low <= high) {
// Get the mid element
var mid = parseInt((low + high) / 2);
var sum = 0;
// Calculate the sum after dividing
// the array by new K which is mid
for (i = 0; i < n; i++) {
sum += parseInt( (a[i] / mid));
}
// Search in the second half
if (sum > s)
low = mid + 1;
// First half
else {
ans = Math.min(ans, mid);
high = mid - 1;
}
}
return ans;
}
// Driver code
var a = [ 10, 7, 8, 10, 12, 19 ];
var n = a.length;
var s = 27;
document.write(findMinimumK(a, n, s));
// This code is contributed by todaysgaurav
</script>
3
Complejidad de tiempo: O(N*(log N)), N=Longitud de array
Espacio Auxiliar: O(1)