Dada una array arr[] que consta de N enteros positivos y un entero positivo M , la tarea es encontrar el entero más pequeño posible K tal que ceil(arr[0]/K) + ceil(arr[1]/K) +… .+ ceil(arr[N – 1]/K) es como máximo M .
Ejemplos:
Entrada: arr[] = {4, 3, 2, 7}, M = 5
Salida: 4
Explicación:
Para K = 4, el valor de ceil(4/4) + ceil(3/4) + ceil(2/ 4) + ceil(7/4) = 1 + 1 + 1 + 2 = 5. Por lo tanto, imprima 5.Entrada: arr[] = {1, 2, 3}, M = 4
Salida: 2
Planteamiento: La idea es utilizar la Búsqueda Binaria . Establezca el valor bajo como 1 y el valor alto como el valor máximo de la array arr[] y encuentre el valor K que es menor o igual que M aplicando la búsqueda binaria. Siga los pasos a continuación para resolver el problema:
- Inicialice las variables, digamos low = 1 y high como el elemento de array máximo .
- Iterar durante un ciclo while hasta alto – bajo > 1 y realizar las siguientes tareas:
- Actualice el valor de mid by mid = (low + high)/2 .
- Recorra la array arr[] y encuentre la suma de ceil(arr[i]/K) asumiendo que mid es K .
- Si la suma es mayor que M , actualice el valor de alto a alto = medio . De lo contrario, actualice el valor de bajo a bajo = medio + 1 .
- Después de completar los pasos anteriores, imprima el valor de low si la suma es como máximo M . De lo contrario, imprima el valor de alto .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the sum of ceil
// values of the arr[] for the K value
// is at most M or not
bool isvalid(int arr[], int K, int N, int M)
{
// Stores the sum of ceil values
int sum = 0;
for (int i = 0; i < N; i++) {
// Update the sum
sum += (int)ceil(arr[i] * 1.0 / K);
}
// Return true if sum is less than
// or equal to M, false otherwise
return sum <= M;
}
// Function to find the smallest possible
// integer K such that ceil(arr[0]/K) +
// ceil(arr[1]/K) +....+ ceil(arr[N-1]/K)
// is less than or equal to M
int smallestValueForK(int arr[], int N, int M)
{
// Stores the low value
int low = 1;
// Stores the high value
int high = *max_element(arr, arr + N);
// Stores the middle value
int mid;
while (high - low > 1) {
// Update the mid value
mid = (high + low) / 2;
// Check if the mid value is K
if (!isvalid(arr, mid, N, M))
// Update the low value
low = mid + 1;
else
// Update the high value
high = mid;
}
// Check if low is K or high is K
// and return it
return isvalid(arr, low, N, M) ? low : high;
}
// Driver Code
int main()
{
int arr[] = { 4, 3, 2, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
int M = 5;
cout << smallestValueForK(arr, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to check if the sum of ceil
// values of the arr[] for the K value
// is at most M or not
static boolean isvalid(int[] arr, int K, int N, int M)
{
// Stores the sum of ceil values
int sum = 0;
for (int i = 0; i < N; i++) {
// Update the sum
sum += Math.ceil(arr[i] * 1.0 / K);
}
// Return true if sum is less than
// or equal to M, false otherwise
return sum <= M;
}
// Function to find the smallest possible
// integer K such that ceil(arr[0]/K) +
// ceil(arr[1]/K) +....+ ceil(arr[N-1]/K)
// is less than or equal to M
static int smallestValueForK(int[] arr, int N, int M)
{
// Stores the low value
int low = 1;
// Stores the high value
int high = arr[0];
//Loop through the array
for (int i = 0; i < arr.length; i++) {
//Compare elements of array with max
if(arr[i] > high)
high = arr[i];
}
// Stores the middle value
int mid;
while (high - low > 1) {
// Update the mid value
mid = (high + low) / 2;
// Check if the mid value is K
if (isvalid(arr, mid, N, M)==false)
// Update the low value
low = mid + 1;
else
// Update the high value
high = mid;
}
// Check if low is K or high is K
// and return it
return isvalid(arr, low, N, M) ? low : high;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 4, 3, 2, 7 };
int N = arr.length;
int M = 5;
System.out.print(smallestValueForK(arr, N, M));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Python3
# python program for the above approach import math # Function to check if the sum of ceil # values of the arr[] for the K value # is at most M or not def isvalid(arr, K, N, M): # Stores the sum of ceil values sum = 0 for i in range(0, N): # Update the sum sum += math.ceil(arr[i] * 1.0 / K) # Return true if sum is less than # or equal to M, false otherwise return sum <= M # Function to find the smallest possible # integer K such that ceil(arr[0]/K) + # ceil(arr[1]/K) +....+ ceil(arr[N-1]/K) # is less than or equal to M def smallestValueForK(arr, N, M): # Stores the low value low = 1 # Stores the high value high = arr[0] for i in range(1, len(arr)): high = max(high, arr[i]) # Stores the middle value mid = 0 while (high - low > 1): # Update the mid value mid = (high + low) // 2 # Check if the mid value is K if (not isvalid(arr, mid, N, M)): # Update the low value low = mid + 1 else: # Update the high value high = mid # Check if low is K or high is K # and return it if(isvalid(arr, low, N, M)): return low else: return high # Driver Code if __name__ == "__main__": arr = [4, 3, 2, 7] N = len(arr) M = 5 print(smallestValueForK(arr, N, M)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Linq;
class GFG {
// Function to check if the sum of ceil
// values of the arr[] for the K value
// is at most M or not
static bool isvalid(int[] arr, int K, int N, int M)
{
// Stores the sum of ceil values
int sum = 0;
for (int i = 0; i < N; i++) {
// Update the sum
sum += (int)Math.Ceiling(arr[i] * 1.0 / K);
}
// Return true if sum is less than
// or equal to M, false otherwise
return sum <= M;
}
// Function to find the smallest possible
// integer K such that ceil(arr[0]/K) +
// ceil(arr[1]/K) +....+ ceil(arr[N-1]/K)
// is less than or equal to M
static int smallestValueForK(int[] arr, int N, int M)
{
// Stores the low value
int low = 1;
// Stores the high value
int high = arr.Max();
// Stores the middle value
int mid;
while (high - low > 1) {
// Update the mid value
mid = (high + low) / 2;
// Check if the mid value is K
if (!isvalid(arr, mid, N, M))
// Update the low value
low = mid + 1;
else
// Update the high value
high = mid;
}
// Check if low is K or high is K
// and return it
return isvalid(arr, low, N, M) ? low : high;
}
// Driver Code
public static void Main()
{
int[] arr = { 4, 3, 2, 7 };
int N = arr.Length;
int M = 5;
Console.WriteLine(smallestValueForK(arr, N, M));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to check if the sum of ceil
// values of the arr[] for the K value
// is at most M or not
function isvalid(arr, K, N, M)
{
// Stores the sum of ceil values
let sum = 0;
for (let i = 0; i < N; i++) {
// Update the sum
sum += Math.ceil(arr[i] * 1.0 / K);
}
// Return true if sum is less than
// or equal to M, false otherwise
return sum <= M;
}
// Function to find the smallest possible
// integer K such that ceil(arr[0]/K) +
// ceil(arr[1]/K) +....+ ceil(arr[N-1]/K)
// is less than or equal to M
function smallestValueForK(arr, N, M) {
// Stores the low value
let low = 1;
// Stores the high value
let high = Number.MIN_VALUE;
for (let i = 0; i < N; i++) {
high = Math.max(high, arr[i]);
}
// Stores the middle value
let mid;
while (high - low > 1) {
// Update the mid value
mid = (high + low) / 2;
// Check if the mid value is K
if (!isvalid(arr, mid, N, M))
// Update the low value
low = mid + 1;
else
// Update the high value
high = mid;
}
// Check if low is K or high is K
// and return it
return isvalid(arr, low, N, M) ? low : high;
}
// Driver Code
let arr = [4, 3, 2, 7];
let N = arr.length;
let M = 5;
document.write(smallestValueForK(arr, N, M));
// This code is contributed by Potta Lokesh
</script>
Producción:
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA