Dada una array arr[] de tamaño N y un entero positivo K , la tarea es encontrar el entero positivo más pequeño tal que la suma de los elementos restantes de la array obtenidos al dividir todos los elementos de la array por ese entero positivo más pequeño no exceda K .
Nota: La división de un elemento de array por el entero positivo más pequeño debe ser del tipo Ceil .
Ejemplos:
Entrada: arr[] = {1, 2, 5, 9}, K = 6
Salida: 5
Explicación:
Dividir todos los elementos de la array por 5 modifica arr[] a {1, 1, 1, 2}.
Dado que la suma de los elementos del arreglo es igual a 5 (< K), la salida requerida es 5.Entrada: arr[]= {2, 3, 5, 7, 11}, K = 11
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver este problema es encontrar el elemento más grande en la array , digamos Max , e iterar sobre el rango [1, Max] usando la variable i y verificar si la suma de los elementos restantes de la array después de dividir todo los elementos de la array por i son menores o iguales a K o no. Si se encuentra que es cierto, imprima i .
Complejidad de tiempo: O(N * Max), donde Max es el elemento más grande de la array.
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la técnica de búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos Max , para almacenar el elemento más grande presente en la array .
- El valor del entero positivo más pequeño que divide todos los elementos de la array para obtener la suma de los elementos de la array restantes menores o iguales a K debe estar en el rango [1, Max] . Por lo tanto, aplique la búsqueda binaria en el rango [1, Max] .
- Inicialice dos variables, digamos left = 1 y right = Max , para almacenar el rango en el que se encuentra el valor de la salida requerida.
- Compruebe si es posible obtener la suma de los elementos de la array menor o igual a K dividiendo los elementos de la array por (izquierda + derecha) / 2 o no. Si se determina que es cierto, actualice right = (left + right) / 2 .
- De lo contrario, actualice left = (left + right) /2 .
- Finalmente, imprima el valor de left .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest positive integer
// that divides array elements to get the sum <= K
int findSmallestInteger(int arr[], int N, int K)
{
// Stores minimum possible of the smallest
// positive integer satisfying the condition
int left = 1;
// Stores maximum possible of the smallest
// positive integer satisfying the condition
int right = *max_element(arr, arr + N);
// Apply binary search over
// the range [left, right]
while (left < right) {
// Stores middle element
// of left and right
int mid = (left + right) / 2;
// Stores sum of
// array elements
int sum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update sum
sum += (arr[i] + mid - 1) / mid;
}
// If sum is greater than K
if (sum > K) {
// Update left
left = mid + 1;
}
else {
// Update right
right = mid;
}
}
return left;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 5, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
;
int K = 6;
cout << findSmallestInteger(arr, N, K);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the smallest positive integer
// that divides array elements to get the sum <= K
static int findSmallestInteger(int arr[],
int N, int K)
{
// Stores minimum possible of the smallest
// positive integer satisfying the condition
int left = 1;
// Stores maximum possible of the smallest
// positive integer satisfying the condition
int right = Arrays.stream(arr).max().getAsInt();
// Apply binary search over
// the range [left, right]
while (left < right)
{
// Stores middle element
// of left and right
int mid = (left + right) / 2;
// Stores sum of
// array elements
int sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update sum
sum += (arr[i] + mid - 1) / mid;
}
// If sum is greater than K
if (sum > K)
{
// Update left
left = mid + 1;
}
else
{
// Update right
right = mid;
}
}
return left;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 2, 5, 9 };
int N = arr.length;
int K = 6;
System.out.println(findSmallestInteger(arr, N, K));
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program to implement # the above approach # Function to find the smallest positive integer # that divides array elements to get the sum <= K def findSmallestInteger(arr, N, K): # Stores minimum possible of the smallest # positive integer satisfying the condition left = 1 # Stores maximum possible of the smallest # positive integer satisfying the condition right = max(arr) # Apply binary search over # the range [left, right] while (left < right): # Stores middle element # of left and right mid = (left + right) // 2 # Stores sum of # array elements sum = 0 # Traverse the array for i in range(N): # Update sum sum += (arr[i] + mid - 1) // mid # If sum is greater than K if (sum > K): # Update left left = mid + 1 else: # Update right right = mid return left # Driver Code if __name__ == '__main__': arr = [1, 2, 5, 9] N = len(arr) K = 6 print(findSmallestInteger(arr, N, K)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Linq;
class GFG{
// Function to find the smallest positive integer
// that divides array elements to get the sum <= K
static int findSmallestInteger(int[] arr,
int N, int K)
{
// Stores minimum possible of the smallest
// positive integer satisfying the condition
int left = 1;
// Stores maximum possible of the smallest
// positive integer satisfying the condition
int right = arr.Max();
// Apply binary search over
// the range [left, right]
while (left < right)
{
// Stores middle element
// of left and right
int mid = (left + right) / 2;
// Stores sum of
// array elements
int sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update sum
sum += (arr[i] + mid - 1) / mid;
}
// If sum is greater than K
if (sum > K)
{
// Update left
left = mid + 1;
}
else
{
// Update right
right = mid;
}
}
return left;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 5, 9 };
int N = arr.Length;
int K = 6;
Console.Write(findSmallestInteger(arr, N, K));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the smallest positive integer
// that divides array elements to get the sum <= K
function findSmallestInteger(arr, N, K)
{
// Stores minimum possible of the smallest
// positive integer satisfying the condition
var left = 1;
// Stores maximum possible of the smallest
// positive integer satisfying the condition
var right = arr.reduce((a, b) => Math.max(a, b));
// Apply binary search over
// the range [left, right]
while (left < right)
{
// Stores middle element
// of left and right
var mid = (left + right) / 2;
// Stores sum of
// array elements
var sum = 0;
// Traverse the array
for(var i = 0; i < N; i++)
{
// Update sum
sum += parseInt((arr[i] + mid - 1) / mid);
}
// If sum is greater than K
if (sum > K)
{
// Update left
left = mid + 1;
}
else
{
// Update right
right = mid;
}
}
return left;
}
// Driver Code
var arr = [ 1, 2, 5, 9 ];
var N = arr.length;
var K = 6;
document.write(findSmallestInteger(arr, N, K));
// This code is contributed by importantly
</script>
5
Complejidad de tiempo: O(N * log(Max)), donde Max es el elemento más grande de la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA