Dada una array arr[] de tamaño N . La tarea es maximizar el valor mínimo de la array después de realizar las operaciones dadas. En una operación, se puede elegir el valor x y
- Se puede restar un valor 3 * x del elemento arr[i] .
- Se agrega un valor x a arr[i-1] . y
- Se puede agregar un valor de 2 * x a arr[i-2] .
Encuentre el elemento mínimo máximo posible de la array después de tales operaciones.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6}
Salida: 3
Explicación: Se elige el último elemento y se puede elegir x =1 .
Entonces 3*x se resta de arr[i] y x se agrega a arr[i-1] y 2*x a arr[i-2] por lo que la array se convierte en {1, 2, 3, 6, 6, 3}
En el cuarto índice , se puede elegir x = 1 y ahora la array se convierte en {1, 2, 5, 7, 3, 3}.
En el tercer índice , se puede elegir x = 1 y ahora la array se convierte en {1, 4, 6, 4, 3, 3}.
En el segundo índice, nuevamente se puede elegir x = 1 y ahora la array se convierte en {3, 4, 3, 4, 3, 3, 3}.
Por lo tanto, el valor mínimo máximo posible es 3.Entrada: arr[] = {9, 13, 167}
Salida: 51
Enfoque ingenuo: este problema se puede resolver comprobando la posibilidad del valor mínimo máximo posible de [1, max(array)] realizando las operaciones desde el final de la array.
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(1)
Enfoque eficiente: El enfoque eficiente de este problema se basa en la búsqueda binaria . Dado que se basa en maximizar el valor mínimo, al aplicar la búsqueda binaria en el rango [1, max (array)] y verificar si mid es posible como un elemento mínimo realizando las operaciones en la array de modo que cada elemento sea >= medio. Siga los pasos a continuación para resolver el problema dado:
- Inicialice f = 1 y l = elemento máximo de la array y la res como INT_MIN .
- Realizar búsqueda binaria mientras f<=l
- Compruebe si mid puede ser el elemento mínimo realizando operaciones en la función is_possible_min() .
- En la función is_possible_min()
- Recorra desde el final de la array (N-1) hasta el índice 2 y verifique si arr[i]<mid si es verdadero devuelve 0 .
- De lo contrario, encuentre el extra que es 3x que se puede agregar a arr[i-1] como x y arr[i-2] como 2x .
- Si arr[0] >=mid y arr[1] >=mid devuelven 1.
- De lo contrario, devuelve 0 .
- En la función is_possible_min()
- Si la función is_possible_min() devuelve verdadero, entonces mid es posible como el valor mínimo almacena max(res, mid) en la variable res, así que maximiza el valor mínimo moviéndote hacia la derecha como f=mid +1
- De lo contrario, muévase hacia la izquierda e intente si es posible por l = mid -1 .
- Imprime la res .
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;
// Check if mid is possible as
// a minimum element after
// any number of operations using
// this predicate function
bool is_possible_min(vector<int> arr,
int mid)
{
int N = arr.size();
// Traverse from the end
for (int i = N - 1; i >= 2; i--) {
// mid can't be minimum
if (arr[i] < mid)
return 0;
else {
// Find the 3x
int extra = arr[i] - mid;
// Find the x
extra /= 3;
// Add x to a[i-1]
arr[i - 1] += extra;
// Add 2x to a[i-2]
arr[i - 2] += 2 * extra;
}
}
// Check if the first two elements
// are >= mid because if every element
// is greater than or equal to
// mid we can conclude
// mid as a minimum element
if (arr[0] >= mid && arr[1] >= mid)
return 1;
return 0;
}
// Function to find the
// maximum possible minimum value
void find_maximum_min(vector<int> arr)
{
// Initialize f = 1 and l as the
// maximum element of the array
int f = 1, l = *max_element(arr.begin(),
arr.end());
// Initialize res as INT_MIN
int res = INT_MIN;
// Perform binary search while f<=l
while (f <= l) {
int mid = (f + l) / 2;
// Check if mid is possible
// as a minimum element
if (is_possible_min(arr, mid)) {
// Take the max value of mid
res = max(res, mid);
// Try maximizing the min value
f = mid + 1;
}
// Move left if it is not possible
else {
l = mid - 1;
}
}
// Print the result
cout << res << endl;
}
// Driver Code
int main()
{
// Initialize the array
vector<int> arr = { 1, 2, 3, 4, 5, 6 };
// Function call
find_maximum_min(arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Check if mid is possible as
// a minimum element after
// any number of operations using
// this predicate function
static Boolean is_possible_min(int arr[],
int mid)
{
int N = arr.length;
// Traverse from the end
for (int i = N - 1; i >= 2; i--) {
// mid can't be minimum
if (arr[i] < mid)
return false;
else {
// Find the 3x
int extra = arr[i] - mid;
// Find the x
extra /= 3;
// Add x to a[i-1]
arr[i - 1] += extra;
// Add 2x to a[i-2]
arr[i - 2] += 2 * extra;
}
}
// Check if the first two elements
// are >= mid because if every element
// is greater than or equal to
// mid we can conclude
// mid as a minimum element
if (arr[0] >= mid && arr[1] >= mid)
return true;
return false;
}
// Function to find the
// maximum possible minimum value
static void find_maximum_min(int arr[])
{
// Initialize f = 1 and l as the
// maximum element of the array
int f = 1, l = Arrays.stream(arr).max().getAsInt();
// Initialize res as INT_MIN
int res = Integer.MIN_VALUE;
// Perform binary search while f<=l
while (f <= l) {
int mid = l + (f - l) / 2;
// Check if mid is possible
// as a minimum element
if (is_possible_min(arr, mid) == true) {
// Take the max value of mid
res = Math.max(res, mid);
// Try maximizing the min value
f = mid + 1;
}
// Move left if it is not possible
else {
l = mid - 1;
}
}
// Print the result
System.out.println(res);
}
// Driver Code
public static void main (String[] args)
{
// Initialize the array
int arr[] = { 1, 2, 3, 4, 5, 6 };
// Function call
find_maximum_min(arr);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# python3 program for the above approach INT_MIN = -2147483647 - 1 # Check if mid is possible as # a minimum element after # any number of operations using # this predicate function def is_possible_min(arr, mid): N = len(arr) # Traverse from the end for i in range(N-1, 1, -1): # mid can't be minimum if (arr[i] < mid): return 0 else: # Find the 3x extra = arr[i] - mid # Find the x extra //= 3 # Add x to a[i-1] arr[i - 1] += extra # Add 2x to a[i-2] arr[i - 2] += 2 * extra # Check if the first two elements # are >= mid because if every element # is greater than or equal to # mid we can conclude # mid as a minimum element if (arr[0] >= mid and arr[1] >= mid): return 1 return 0 # Function to find the # maximum possible minimum value def find_maximum_min(arr): # Initialize f = 1 and l as the # maximum element of the array f, l = 1, max(arr) # Initialize res as INT_MIN res = INT_MIN # Perform binary search while f<=l while (f <= l): mid = (f + l) // 2 # print(is_possible_min(arr,mid)) # Check if mid is possible # as a minimum element if (is_possible_min(arr.copy(), mid)): # Take the max value of mid res = max(res, mid) # Try maximizing the min value f = mid + 1 # Move left if it is not possible else: l = mid - 1 # Print the result print(res) # Driver Code if __name__ == "__main__": # Initialize the array arr = [1, 2, 3, 4, 5, 6] # Function call find_maximum_min(arr) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Linq;
class GFG
{
// Check if mid is possible as
// a minimum element after
// any number of operations using
// this predicate function
static bool is_possible_min(int[] arr, int mid)
{
int N = arr.Length;
// Traverse from the end
for (int i = N - 1; i >= 2; i--) {
// mid can't be minimum
if (arr[i] < mid)
return false;
else {
// Find the 3x
int extra = arr[i] - mid;
// Find the x
extra /= 3;
// Add x to a[i-1]
arr[i - 1] += extra;
// Add 2x to a[i-2]
arr[i - 2] += 2 * extra;
}
}
// Check if the first two elements
// are >= mid because if every element
// is greater than or equal to
// mid we can conclude
// mid as a minimum element
if (arr[0] >= mid && arr[1] >= mid)
return true;
return false;
}
// Function to find the
// maximum possible minimum value
static void find_maximum_min(int[] arr)
{
// Initialize f = 1 and l as the
// maximum element of the array
int f = 1, l = arr.Max();
// Initialize res as INT_MIN
int res = Int32.MinValue;
// Perform binary search while f<=l
while (f <= l) {
int mid = l + (f - l) / 2;
// Check if mid is possible
// as a minimum element
if (is_possible_min(arr, mid) == true) {
// Take the max value of mid
res = Math.Max(res, mid);
// Try maximizing the min value
f = mid + 1;
}
// Move left if it is not possible
else {
l = mid - 1;
}
}
// Print the result
Console.WriteLine(res);
}
// Driver Code
public static void Main()
{
// Initialize the array
int[] arr = { 1, 2, 3, 4, 5, 6 };
// Function call
find_maximum_min(arr);
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// Javascript program for the above approach
// Check if mid is possible as
// a minimum element after
// any number of operations using
// this predicate function
function is_possible_min(arr, mid) {
let N = arr.length;
// Traverse from the end
for (let i = N - 1; i >= 2; i--) {
// mid can't be minimum
if (arr[i] < mid)
return 0;
else {
// Find the 3x
let extra = arr[i] - mid;
// Find the x
extra = Math.floor(extra / 3);
// Add x to a[i-1]
arr[i - 1] += extra;
// Add 2x to a[i-2]
arr[i - 2] += 2 * extra;
}
}
// Check if the first two elements
// are >= mid because if every element
// is greater than or equal to
// mid we can conclude
// mid as a minimum element
if (arr[0] >= mid && arr[1] >= mid)
return 1;
return 0;
}
// Function to find the
// maximum possible minimum value
function find_maximum_min(arr) {
// Initialize f = 1 and l as the
// maximum element of the array
let f = 1, l = max_element(arr);
// Initialize res as INT_MIN
let res = Number.MIN_SAFE_INTEGER
// Perform binary search while f<=l
while (f <= l) {
let mid = Math.ceil((f + l) / 2);
// Check if mid is possible
// as a minimum element
if (is_possible_min(arr, mid)) {
// Take the max value of mid
res = Math.max(res, mid);
// Try maximizing the min value
f = mid + 1;
}
// Move left if it is not possible
else {
l = mid - 1;
}
}
// Print the result
document.write(res);
}
function max_element(ar) {
return [...ar].sort((a, b) => - a + b)[0]
}
// Driver Code
// Initialize the array
let arr = [1, 2, 3, 4, 5, 6];
// Function call
find_maximum_min(arr);
// This code is contributed by saurabh_jaiswal.
</script>
Producción
3
Complejidad de tiempo: O(N* log(maxval)) donde maxval es el elemento máximo de la array. Como estamos usando un bucle while para atravesar log(marval) veces, estamos decrementando por división de piso de 2 cada recorrido, y la función is_possible_min costará O (N) ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA