Dada una array arr[] de n elementos, actualice todos los elementos de la array dada a algún valor mínimo x, es decir, arr[i] = x (0 <= i < n), de modo que el producto de todos los elementos de esta nueva array sea estrictamente mayor que el producto de todos los elementos de la array inicial, donde 1 <= arr[i] <= 10^10 y 1 <= n <= 10^5
Ejemplos:
Input : arr[] = [4, 2, 1, 10, 6] Output : 4 4 is the smallest value such that 4 * 4 * 4 * 4 * 4 > 4 * 2 * 1 * 10 * 6 Input : arr[] = [100, 150, 10000, 123458, 90980454] Output : 17592
Método 1: O(n registro n):
Usamos la búsqueda binaria en los límites de n. En cada mid, verificamos si el producto de mid n es mayor que el producto original de la array o no.
Utilizamos registro de productos para evitar el desbordamiento. Entonces calculamos el registro del producto actual y el registro de mid n durante la búsqueda binaria para comparar valores.
Implementación:
C++
// C++ program to find minimum value that can
// be assigned to all elements so that product
// becomes greater than current product.
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
ll findMinValue(ll arr[], ll n)
{
// sort the array to apply Binary search
sort(arr, arr+n);
// using log property add every logarithmic
// value of element to val
ld val = 0; // where ld is long double
for (int i=0; i<n; i++)
val += (ld)(log((ld)(arr[i])));
// set left and right extremities to find
// min value
ll left = arr[0], right = arr[n-1]+1;
ll ans;
while (left<=right)
{
ll mid = (left+right)/2;
// multiplying n to mid, to find the
// correct min value
ld temp = (ld)n * (ld)(log((ld)(mid)));
if (val < temp)
{
ans = mid;
right = mid-1;
}
else
left = mid+1;
}
return ans;
}
// Driver code
int main()
{
ll arr[] = {4, 2, 1, 10, 6};
ll n = sizeof(arr)/sizeof(arr[0]);
cout << findMinValue(arr, n) << endl;
return 0;
}
Java
import java.util.Arrays;
// Java program to find minimum value that can
// be assigned to along elements so that product
// becomes greater than current product.
class GFG1 {
static long findMinValue(long arr[], int n) {
// sort the array to apply Binary search
Arrays.sort(arr);
// using log property add every logarithmic
// value of element to val
double val = 0; // where double is long double
for (int i = 0; i < n; i++) {
val += (double) (Math.log((double) (arr[i])));
}
// set left and right extremities to find
// min value
long left = arr[0], right = arr[n - 1];
long ans = 0;
while (left <= right) {
long mid = (left + right) / 2;
// multiplying n to mid, to find the
// correct min value
double temp = (double) n * (double) (Math.log((double) (mid)));
if (val < temp) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
// Driver code
public static void main(String[] args) {
long arr[] = {4, 2, 1, 10, 6};
int n = arr.length;
System.out.println(findMinValue(arr, n));
}
}
//This code is contributed by 29AjayKumar
Python3
# Python3 program to find minimum # value that can be assigned to all # elements so that product becomes # greater than current product. import math def findMinValue(arr, n): # sort the array to apply # Binary search arr.sort() # using log property add every # logarithmic value of element to val val = 0 # where ld is long double for i in range(n): val += (math.log(arr[i])) # set left and right extremities to find # min value left = arr[0] right = arr[n - 1] + 1 while (left <= right): mid = (left + right) // 2 # multiplying n to mid, to find # the correct min value temp = n * (math.log(mid)) if (val < temp): ans = mid right = mid - 1 else: left = mid + 1 return ans # Driver code if __name__ == "__main__": arr = [4, 2, 1, 10, 6] n = len(arr) print(findMinValue(arr, n) ) # This code is contributed # by ChitraNayal
C#
// C# program to find minimum value that can
// be assigned to along elements so that product
// becomes greater than current product.
using System;
public class GFG{
static long findMinValue(long []arr, int n) {
// sort the array to apply Binary search
Array.Sort(arr);
// using log property add every logarithmic
// value of element to val
double val = 0; // where double is long double
for (int i = 0; i < n; i++) {
val += (double) (Math.Log((double) (arr[i])));
}
// set left and right extremities to find
// min value
long left = arr[0], right = arr[n - 1];
long ans = 0;
while (left <= right) {
long mid = (left + right) / 2;
// multiplying n to mid, to find the
// correct min value
double temp = (double) n * (double) (Math.Log((double) (mid)));
if (val < temp) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
// Driver code
static public void Main (){
long []arr = {4, 2, 1, 10, 6};
int n = arr.Length;
Console.WriteLine(findMinValue(arr, n));
}
//This code is contributed by ajit.
}
PHP
<?php
// PHP program to find minimum value that can
// be assigned to all elements so that product
// becomes greater than current product.
function findMinValue($arr, $n)
{
// sort the array to apply Binary search
sort($arr);
// using log property add every logarithmic
// value of element to val
$val = 0; // where ld is long double
for ($i = 0; $i < $n; $i++)
$val += (log($arr[$i]));
// set left and right extremities
// to find min value
$left = $arr[0];
$right = $arr[$n - 1] + 1;
$ans = 0;
while ($left <= $right)
{
$mid = (int)($left + $right) / 2;
// multiplying n to mid, to find
// the correct min value
$temp = $n * (log($mid));
if ($val < $temp)
{
$ans = $mid;
$right = $mid - 1;
}
else
$left = $mid + 1;
}
return (floor($ans));
}
// Driver code
$arr = array(4, 2, 1, 10, 6);
$n = sizeof($arr);
echo findMinValue($arr, $n), "\n";
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to find minimum value that can
// be assigned to along elements so that product
// becomes greater than current product.
function findMinValue(arr,n)
{
// sort the array to apply Binary search
arr.sort(function(a,b){return a-b;});
// using log property add every logarithmic
// value of element to val
let val = 0; // where double is long double
for (let i = 0; i < n; i++) {
val += (Math.log( (arr[i])));
}
// set left and right extremities to find
// min value
let left = arr[0], right = arr[n - 1];
let ans = 0;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
// multiplying n to mid, to find the
// correct min value
let temp = n * (Math.log((mid)));
if (val < temp) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
// Driver code
let arr=[4, 2, 1, 10, 6];
let n = arr.length;
document.write(findMinValue(arr, n));
// This code is contributed by rag2127
</script>
Producción
4
Solución 2 : O(n)
Al saber el hecho de que el producto de n elementos es P, si tenemos que encontrar la raíz n-ésima de P. Para encontrar la raíz n-ésima del producto, simplemente podemos dividir n de la suma del registro de n elementos de la array y luego techo de antilog será nuestra respuesta al problema, es decir,
ans = ceil(antilog(log(x)/n))
ans = ceil(potencia(10, log(x)/n))
Implementación:
C++
// C++ program to find minimum value to assign all
// array elements so that array product becomes greater
#include <bits/stdc++.h>
using namespace std;
// Epsilon value is used at various steps
// to ensure correctness upto 10^15 digits.
#define EPS 1e-15
#define ll long long int
ll findMinValue(ll arr[], ll n)
{
// add logarithmic value of all elements to sum
long double sum = 0;
for (int i=0; i<n; i++)
sum += (long double)log10(arr[i])+EPS;
// to find the nth root of sum
long double xl = (long double)(sum/n+EPS);
// to find the antilog of xl
long double res = pow((long double)10.0, (long double)xl) + EPS;
return (ll)ceil(res+EPS);
}
// Driver code
int main()
{
ll arr[] = {4, 2, 1, 10, 6};
ll n = sizeof(arr)/sizeof(arr[0]);
printf("%lld", findMinValue(arr, n));
return 0;
}
Java
// Java program to find minimum value to assign all array
// elements so that array product becomes greater
class GFG{
// Epsilon value is used at various steps
// to ensure correctness upto 10^15 digits.
static double EPS=1E-15;
static double findMinValue(double arr[], double n)
{
// add logarithmic value of all elements to sum
double sum = 0;
for (int i=0; i<n; i++)
sum += (double)Math.log10(arr[i])+EPS;
// to find the nth root of sum
double xl = (double)(sum/n+EPS);
// to find the antilog of xl
double res = Math.pow((double)10.0, (double)xl) + EPS;
return (double)Math.ceil(res+EPS);
}
// Driver code
public static void main(String[] args)
{
double arr[] = {4, 2, 1, 10, 6};
double n = arr.length;
System.out.println(findMinValue(arr, n));
}
}
// This code is contributed by mits
Python3
# Epsilon value is used at various steps # to ensure correctness upto 10^15 digits. import math EPS = 1E-15; def findMinValue(arr, n): # add logarithmic value of all # elements to sum sum = 0; for i in range(n): sum += math.log10(arr[i]) + EPS; # to find the nth root of sum xl = (sum / n + EPS); # to find the antilog of xl res = math.pow(10.0, xl) + EPS; return math.ceil(res + EPS); # Driver code arr = [4, 2, 1, 10, 6]; n = len(arr); print(findMinValue(arr, n)); # This code is contributed by mits
C#
// C# program to find minimum value to assign all
// array elements so that array product becomes greater
using System;
class GFG{
// Epsilon value is used at various steps
// to ensure correctness upto 10^15 digits.
static double EPS=1E-15;
static double findMinValue(double[] arr, double n)
{
// add logarithmic value of all elements to sum
double sum = 0;
for (int i=0; i<n; i++)
sum += (double)Math.Log10(arr[i])+EPS;
// to find the nth root of sum
double xl = (double)(sum/n+EPS);
// to find the antilog of xl
double res = Math.Pow((double)10.0, (double)xl) + EPS;
return (double)Math.Ceiling(res+EPS);
}
// Driver code
public static void Main()
{
double[] arr = {4, 2, 1, 10, 6};
double n = arr.Length;
Console.WriteLine(findMinValue(arr, n));
}
}
// This code is contributed by mits
PHP
<?php
// Epsilon value is used at various steps
// to ensure correctness upto 10^15 digits.
$EPS = 1E-15;
function findMinValue($arr, $n)
{
global $EPS;
// add logarithmic value of all
# elements to sum
$sum = 0;
for ($i = 0; $i < $n; $i++)
$sum += log10($arr[$i]) + $EPS;
// to find the nth root of sum
$xl = ($sum / $n + $EPS);
// to find the antilog of xl
$res = pow(10.0, $xl) + $EPS;
return ceil($res + $EPS);
}
// Driver code
$arr = array(4, 2, 1, 10, 6);
$n = count($arr);
print(findMinValue($arr, $n));
// This code is contributed by mits
?>
Javascript
<script>
// javascript program to find minimum value to assign all array
// elements so that array product becomes greater
// Epsilon value is used at various steps
// to ensure correctness upto 10^15 digits.
var EPS = 1E-15;
function findMinValue(arr , n) {
// add logarithmic value of all elements to sum
var sum = 0;
for (i = 0; i < n; i++)
sum += Math.log10(arr[i]) + EPS;
// to find the nth root of sum
var xl = (sum / n + EPS);
// to find the antilog of xl
var res = Math.pow( 10.0, xl) + EPS;
return Math.ceil(res + EPS);
}
// Driver code
var arr = [ 4, 2, 1, 10, 6 ];
var n = arr.length;
document.write(findMinValue(arr, n));
// This code is contributed by todaysgaurav
</script>
Producción
4
Este artículo es una contribución de Abhishek Rajput . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA