Dada una array arr[] de tamaño N y un número K , la tarea es encontrar el número M más pequeño tal que la suma de la array sea menor o igual que el número K cuando cada elemento de esa array se divide por el número m _
Nota: Cada resultado de la división se redondea al entero más cercano mayor o igual a ese elemento. Por ejemplo: 10/3 = 4 y 6/2 = 3
Ejemplos:
Entrada: arr[] = {2, 3, 4, 9}, K = 6
Salida: 4
Explicación:
Cuando cada elemento se divide por 4- 2/4 + 3/4 + 4/4 + 9/4 = 1 + 1 + 1 + 3 = 6
Cuando cada elemento se divide por 3- 2/3 + 3/3 + 4/3 + 9/3 = 1 + 1 + 2 + 3 = 7 que es mayor que K.
Por lo tanto, el más pequeño entero que hace que la suma sea menor o igual a K = 6 es 4.
Entrada: arr[] = {5, 6, 7, 8}, K = 4
Salida: 8
Enfoque ingenuo: el enfoque ingenuo para este problema es comenzar desde 1 y para cada número, dividir cada elemento de la array y verificar si la suma es menor o igual a K. El primer número en el que se cumple esta condición es la respuesta requerida. .
Complejidad temporal: O(N * M) , donde M es el número a encontrar y N es el tamaño de la array.
Enfoque Eficiente: La idea es utilizar el concepto de Búsqueda Binaria .
- Ingrese la array.
- Al asumir que la respuesta máxima posible es 10 9 , inicialice el máximo como 10 9 y el mínimo como 1.
- Realice la búsqueda binaria en este rango y para cada número, verifique si la suma es menor o igual a K.
- Si la suma es menor que K, entonces podría existir una respuesta para un número menor que este. Entonces, continúe y verifique los números menores que ese contador.
- Si la suma es mayor que K, entonces el número M es mayor que el contador actual. Entonces, continúe y verifique los números mayores que ese contador.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the smallest
// number such that the sum of the
// array becomes less than or equal
// to K when every element of the
// array is divided by that number
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest
// number such that the sum of the
// array becomes less than or equal
// to K when every element of the
// array is divided by that number
int findMinDivisor(int arr[], int n, int limit)
{
// Binary search between 1 and 10^9
int low = 0, high = 1e9;
while (low < high) {
int mid = (low + high) / 2;
int sum = 0;
// Calculating the new sum after
// dividing every element by mid
for (int i = 0; i < n; i++) {
sum += ceil((double)arr[i]
/ (double)mid);
}
// If after dividing by mid,
// if the new sum is less than or
// equal to limit move low to mid+1
if (sum <= limit)
high = mid;
else
// Else, move mid + 1 to high
low = mid + 1;
}
// Returning the minimum number
return low;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 6;
cout << findMinDivisor(arr, N, K);
}
Java
// Java program to find the smallest
// number such that the sum of the
// array becomes less than or equal
// to K when every element of the
// array is divided by that number
import java.util.*;
class GFG{
// Function to find the smallest
// number such that the sum of the
// array becomes less than or equal
// to K when every element of the
// array is divided by that number
static int findMinDivisor(int arr[],
int n, int limit)
{
// Binary search between 1 and 10^9
int low = 0, high = 1000000000;
while (low < high)
{
int mid = (low + high) / 2;
int sum = 0;
// Calculating the new sum after
// dividing every element by mid
for(int i = 0; i < n; i++)
{
sum += Math.ceil((double) arr[i] /
(double) mid);
}
// If after dividing by mid,
// if the new sum is less than or
// equal to limit move low to mid+1
if (sum <= limit)
high = mid;
else
// Else, move mid + 1 to high
low = mid + 1;
}
// Returning the minimum number
return low;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 9 };
int N = arr.length;
int K = 6;
System.out.println(
findMinDivisor(arr, N, K));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to find the smallest # number such that the sum of the # array becomes less than or equal # to K when every element of the # array is divided by that number from math import ceil # Function to find the smallest # number such that the sum of the # array becomes less than or equal # to K when every element of the # array is divided by that number def findMinDivisor(arr, n, limit): # Binary search between 1 and 10^9 low = 0 high = 10 ** 9 while (low < high): mid = (low + high) // 2 sum = 0 # Calculating the new sum after # dividing every element by mid for i in range(n): sum += ceil(arr[i] / mid) # If after dividing by mid, # if the new sum is less than or # equal to limit move low to mid+1 if (sum <= limit): high = mid else: # Else, move mid + 1 to high low = mid + 1 # Returning the minimum number return low # Driver code if __name__ == '__main__': arr= [ 2, 3, 4, 9 ] N = len(arr) K = 6 print(findMinDivisor(arr, N, K)) # This code is contributed by mohit kumar 29
C#
// C# program to find the smallest
// number such that the sum of the
// array becomes less than or equal
// to K when every element of the
// array is divided by that number
using System;
class GFG{
// Function to find the smallest
// number such that the sum of the
// array becomes less than or equal
// to K when every element of the
// array is divided by that number
static int findMinDivisor(int []arr, int n,
int limit)
{
// Binary search between 1 and 10^9
int low = 0, high = 1000000000;
while (low < high)
{
int mid = (low + high) / 2;
int sum = 0;
// Calculating the new sum after
// dividing every element by mid
for(int i = 0; i < n; i++)
{
sum += (int)Math.Ceiling((double) arr[i] /
(double) mid);
}
// If after dividing by mid,
// if the new sum is less than or
// equal to limit move low to mid+1
if (sum <= limit)
{
high = mid;
}
else
{
// Else, move mid + 1 to high
low = mid + 1;
}
}
// Returning the minimum number
return low;
}
// Driver Code
public static void Main(String []args)
{
int []arr = { 2, 3, 4, 9 };
int N = arr.Length;
int K = 6;
Console.WriteLine(findMinDivisor(arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Program program to find the smallest
// number such that the sum of the
// array becomes less than or equal
// to K when every element of the
// array is divided by that number
// Function to find the smallest
// number such that the sum of the
// array becomes less than or equal
// to K when every element of the
// array is divided by that number
function findMinDivisor(arr, n, limit)
{
// Binary search between 1 and 10^9
let low = 0, high = 1000000000;
while (low < high)
{
let mid = Math.floor((low + high) / 2);
let sum = 0;
// Calculating the new sum after
// dividing every element by mid
for(let i = 0; i < n; i++)
{
sum += Math.ceil( arr[i] / mid);
}
// If after dividing by mid,
// if the new sum is less than or
// equal to limit move low to mid+1
if (sum <= limit)
high = mid;
else
// Else, move mid + 1 to high
low = mid + 1;
}
// Returning the minimum number
return low;
}
// Driver Code
let arr = [ 2, 3, 4, 9 ];
let N = arr.length;
let K = 6;
document.write(
findMinDivisor(arr, N, K));
</script>
4
Complejidad de tiempo: O(N * 30) , donde N es el tamaño de la array porque encontrar cualquier número entre 1 y 10 9 requiere como máximo 30 operaciones en la búsqueda binaria.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aqibmahboob1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA