Dada una array de tamaño 
y un número 
. La tarea es modificar la array dada de tal manera que:
- La diferencia entre la suma de los elementos del arreglo antes y después de la modificación es exactamente igual a S.
- Los elementos de array modificados deben ser no negativos.
- El valor mínimo en la array modificada debe maximizarse.
- Para modificar la array dada, puede incrementar o disminuir cualquier elemento de la array.
La tarea es encontrar el número mínimo de la array modificada. Si no es posible, imprima -1. El número mínimo debe ser el máximo posible.
Ejemplos:
Input : a[] = {2, 2, 3}, S = 1
Output : 2
Explanation : Modified array is {2, 2, 2}
Input : a[] = {1, 3, 5}, S = 10
Output : -1
Un enfoque eficiente es realizar una búsqueda binaria entre el valor mínimo y máximo posible del número mínimo en una array modificada. El valor mínimo posible es cero y la array máxima posible es el número mínimo en una array determinada. Si la suma de los elementos de la array dada es menor que S, entonces la respuesta no es posible. entonces, imprime -1. Si la suma de los elementos de la array dada es igual a S, la respuesta será cero.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the maximum possible
// value of the minimum value of
// modified array
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum possible value
// of the minimum value of the modified array
int maxOfMin(int a[], int n, int S)
{
// To store minimum value of array
int mi = INT_MAX;
// To store sum of elements of array
int s1 = 0;
for (int i = 0; i < n; i++) {
s1 += a[i];
mi = min(a[i], mi);
}
// Solution is not possible
if (s1 < S)
return -1;
// zero is the possible value
if (s1 == S)
return 0;
// minimum possible value
int low = 0;
// maximum possible value
int high = mi;
// to store a required answer
int ans;
// Binary Search
while (low <= high) {
int mid = (low + high) / 2;
// If mid is possible then try to increase
// required answer
if (s1 - (mid * n) >= S) {
ans = mid;
low = mid + 1;
}
// If mid is not possible then decrease
// required answer
else
high = mid - 1;
}
// Return required answer
return ans;
}
// Driver Code
int main()
{
int a[] = { 10, 10, 10, 10, 10 };
int S = 10;
int n = sizeof(a) / sizeof(a[0]);
cout << maxOfMin(a, n, S);
return 0;
}
Java
// Java program to find the maximum possible
// value of the minimum value of
// modified array
import java.io.*;
class GFG {
// Function to find the maximum possible value
// of the minimum value of the modified array
static int maxOfMin(int a[], int n, int S)
{
// To store minimum value of array
int mi = Integer.MAX_VALUE;
// To store sum of elements of array
int s1 = 0;
for (int i = 0; i < n; i++) {
s1 += a[i];
mi = Math.min(a[i], mi);
}
// Solution is not possible
if (s1 < S)
return -1;
// zero is the possible value
if (s1 == S)
return 0;
// minimum possible value
int low = 0;
// maximum possible value
int high = mi;
// to store a required answer
int ans=0;
// Binary Search
while (low <= high) {
int mid = (low + high) / 2;
// If mid is possible then try to increase
// required answer
if (s1 - (mid * n) >= S) {
ans = mid;
low = mid + 1;
}
// If mid is not possible then decrease
// required answer
else
high = mid - 1;
}
// Return required answer
return ans;
}
// Driver Code
public static void main (String[] args) {
int a[] = { 10, 10, 10, 10, 10 };
int S = 10;
int n = a.length;
System.out.println( maxOfMin(a, n, S));
}
//This code is contributed by ajit.
}
Python
# Python program to find the maximum possible # value of the minimum value of # modified array # Function to find the maximum possible value # of the minimum value of the modified array def maxOfMin(a, n, S): # To store minimum value of array mi = 10**9 # To store sum of elements of array s1 = 0 for i in range(n): s1 += a[i] mi = min(a[i], mi) # Solution is not possible if (s1 < S): return -1 # zero is the possible value if (s1 == S): return 0 # minimum possible value low = 0 # maximum possible value high = mi # to store a required answer ans=0 # Binary Search while (low <= high): mid = (low + high) // 2 # If mid is possible then try to increase # required answer if (s1 - (mid * n) >= S): ans = mid low = mid + 1 # If mid is not possible then decrease # required answer else: high = mid - 1 # Return required answer return ans # Driver Code a=[10, 10, 10, 10, 10] S = 10 n =len(a) print(maxOfMin(a, n, S)) #This code is contributed by Mohit kumar 29
C#
// C# program to find the maximum possible
// value of the minimum value of
// modified array
using System;
class GFG {
// Function to find the maximum possible value
// of the minimum value of the modified array
static int maxOfMin(int []a, int n, int S)
{
// To store minimum value of array
int mi = int.MaxValue;
// To store sum of elements of array
int s1 = 0;
for (int i = 0; i < n; i++) {
s1 += a[i];
mi = Math.Min(a[i], mi);
}
// Solution is not possible
if (s1 < S)
return -1;
// zero is the possible value
if (s1 == S)
return 0;
// minimum possible value
int low = 0;
// maximum possible value
int high = mi;
// to store a required answer
int ans=0;
// Binary Search
while (low <= high) {
int mid = (low + high) / 2;
// If mid is possible then try to increase
// required answer
if (s1 - (mid * n) >= S) {
ans = mid;
low = mid + 1;
}
// If mid is not possible then decrease
// required answer
else
high = mid - 1;
}
// Return required answer
return ans;
}
// Driver Code
public static void Main () {
int []a = { 10, 10, 10, 10, 10 };
int S = 10;
int n = a.Length;
Console.WriteLine(maxOfMin(a, n, S));
}
//This code is contributed by Ryuga
}
PHP
<?php
// PHP program to find the maximum possible
// value of the minimum value of modified array
// Function to find the maximum possible value
// of the minimum value of the modified array
function maxOfMin($a, $n, $S)
{
// To store minimum value
// of array
$mi = PHP_INT_MAX;
// To store sum of elements
// of array
$s1 = 0;
for ($i = 0; $i < $n; $i++)
{
$s1 += $a[$i];
$mi = min($a[$i], $mi);
}
// Solution is not possible
if ($s1 < $S)
return -1;
// zero is the possible value
if ($s1 == $S)
return 0;
// minimum possible value
$low = 0;
// maximum possible value
$high = $mi;
// to store a required answer
$ans;
// Binary Search
while ($low <= $high)
{
$mid = ($low + $high) / 2;
// If mid is possible then try
// to increase required answer
if ($s1 - ($mid * $n) >= $S)
{
$ans = $mid;
$low = $mid + 1;
}
// If mid is not possible then
// decrease required answer
else
$high = $mid - 1;
}
// Return required answer
return $ans;
}
// Driver Code
$a = array( 10, 10, 10, 10, 10 );
$S = 10;
$n = sizeof($a);
echo maxOfMin($a, $n, $S);
// This code is contributed by akt_mit
?>
Javascript
<script>
// Javascript program to find the maximum possible
// value of the minimum value of
// modified array
// Function to find the maximum possible value
// of the minimum value of the modified array
function maxOfMin(a, n, S)
{
// To store minimum value of array
let mi = Number.MAX_VALUE;
// To store sum of elements of array
let s1 = 0;
for (let i = 0; i < n; i++) {
s1 += a[i];
mi = Math.min(a[i], mi);
}
// Solution is not possible
if (s1 < S)
return -1;
// zero is the possible value
if (s1 == S)
return 0;
// minimum possible value
let low = 0;
// maximum possible value
let high = mi;
// to store a required answer
let ans=0;
// Binary Search
while (low <= high) {
let mid = parseInt((low + high) / 2, 10);
// If mid is possible then try to increase
// required answer
if (s1 - (mid * n) >= S) {
ans = mid;
low = mid + 1;
}
// If mid is not possible then decrease
// required answer
else
high = mid - 1;
}
// Return required answer
return ans;
}
let a = [ 10, 10, 10, 10, 10 ];
let S = 10;
let n = a.length;
document.write(maxOfMin(a, n, S));
</script>
Producción:
8
Complejidad de tiempo: O(n + logn)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA