n次方大于大小为n的数组乘积的最小元素-yiteyi-C++库

给定一系列 N 整数。求出分配给每个数组元素的最小x，使这个新数组中所有元素的乘积严格大于初始数组中所有元素的乘积。例如：

null

Input: 4 2 1 10 6 Output: 4 Explanation: Product of elements of initialarray 4*2*1*10*6 = 480. If x = 4 then 4*4*4*4*4 = 480, if x = 3 then 3*3*3*3*3=243. So minimal element = 4   Input: 3 2 1 4 Output: 3Explanation: Product of elements of initialarray 3*2*1*4 = 24. If x = 3 then 3*3*3*3 = 81, if x = 2 then 2*2*2*2 = 243. So minimalelement = 3.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

简单方法： 一种简单的方法是从1开始运行循环，直到我们发现乘积大于初始数组乘积。 时间复杂性 : O（x^n） 如果使用pow函数 O（x*logn） 数学方法：

Let, x^n = a1 * a2 * a3 * a4 *....* anwe have been given n and value of a1, a2, a3, ..., an.Now take log on both sides with base e n*logex > loge(a1) + loge(a2) +......+ loge(an)Lets sum = loge(a1) + loge(a2) + ...... + loge(an) n*loge x > sum loge x > sum/nThen take antilog on both side x > e^(sum/n)

下面是上述方法的实现。

C++

                         // CPP program to find minimum element whose n-th                       
                         // power is greater than product of an array of                       
                         // size n                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to find the minimum element                       
                         int                                     findMin(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 // loop to traverse and store the sum of log                       
                                                 double                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 sum +=                                     log                                     (a[i]);                                     // computes sum                       
           
                                                 // calculates the elements according to formula.                       
                                                 int                                     x =                                     exp                                     (sum / n);                       
           
                                                 // returns the minimal element                       
                                                 return                                     x + 1;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 // initialised array                       
                                                 int                                     a[] = { 3, 2, 1, 4 };                       
           
                                                 // computes the size of array                       
                                                 int                                     n =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
           
                                                 // prints out the minimal element                       
                                                 cout << findMin(a, n);                       
                         }                       

JAVA

                         // JAVA Code to find Minimum element whose                       
                         // n-th power is greater than product of                       
                         // an array of size n                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // function to find the minimum element                       
                                                 static                                     int                                     findMin(                                     int                                     a[],                                     int                                     n)                       
                                                 {                       
                                                 // loop to traverse and store the                       
                                                 // sum of log                       
                                                 double                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                   
                                                 // computes sum                       
                                                 sum += Math.log(a[i]);                       
                                   
                                                 // calculates the elements                       
                                                 // according to formula.                       
                                                 int                                     x = (                                     int                                     )Math.exp(sum / n);                       
                                   
                                                 // returns the minimal element                       
                                                 return                                     x +                                     1                                     ;                       
                                                 }                       
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 // initialised array                       
                                                 int                                     a[] = {                                     3                                     ,                                     2                                     ,                                     1                                     ,                                     4                                     };                       
                                   
                                                 // computes the size of array                       
                                                 int                                     n = a.length;                       
                                   
                                                 // prints out the minimal element                       
                                                 System.out.println(findMin(a, n));                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by Arnav Kr. Mandal.                       

Python3

                         # Python3 program to find minimum element                       
                         # whose n-th power is greater than product                       
                         # of an array of size n                       
                         import                                     math as m                       
           
                         # function to find the minimum element                       
                         def                                     findMin( a, n):                       
                                   
                                                 # loop to traverse and store the                       
                                                 # sum of log                       
                                                 _sum                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 _sum                                     +                                     =                                     m.log(a[i])                                     # computes sum                       
                                   
                                                 # calculates the elements                       
                                                 # according to formula.                       
                                                 x                                     =                                     m.exp(_sum                                     /                                     n)                       
                                   
                                                 # returns the minimal element                       
                                                 return                                     int                                     (x                                     +                                     1                                     )                       
                                   
                         # Driver program to test above function                       
           
                         # initialised array                       
                         a                                     =                                     [                                     3                                     ,                                     2                                     ,                                     1                                     ,                                     4                                     ]                       
           
                         # computes the size of array                       
                         n                                     =                                     len                                     (a)                       
           
                         # prints out the minimal element                       
                         print                                     (findMin(a, n))                       
           
                         # This code is contributed by "Abhishek Sharma 44"                       

C#

                         // C# Code to find Minimum element whose                       
                         // n-th power is greater than product of                       
                         // an array of size n                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // function to find the minimum element                       
                                                 static                                     int                                     findMin(                                     int                                     []a,                                     int                                     n)                       
                                                 {                       
                                   
                                                 // loop to traverse and store the                       
                                                 // sum of log                       
                                                 double                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                   
                                                 // computes sum                       
                                                 sum += Math.Log(a[i]);                       
                                   
                                                 // calculates the elements                       
                                                 // according to formula.                       
                                                 int                                     x = (                                     int                                     )Math.Exp(sum / n);                       
                                   
                                                 // returns the minimal element                       
                                                 return                                     x + 1;                       
                                                 }                       
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                   
                                                 // initialised array                       
                                                 int                                     []a = { 3, 2, 1, 4 };                       
                                   
                                                 // computes the size of array                       
                                                 int                                     n = a.Length;                       
                                   
                                                 // prints out the minimal element                       
                                                 Console.WriteLine(findMin(a, n));                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to find minimum                       
                         // element whose n-th power                       
                         // is greater than product of                       
                         // an array of size n                       
           
                         // function to find the                       
                         // minimum element                       
                         function                                     findMin(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 // loop to traverse and                       
                                                 // store the sum of log                       
                                                 $sum                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                   
                                                 // computes sum                       
                                                 $sum                                     += log(                                     $a                                     [                                     $i                                     ]);                       
           
                                                 // calculates the elements                       
                                                 // according to formula.                       
                                                 $x                                     =                                     exp                                     (                                     $sum                                     /                                     $n                                     );                       
           
                                                 // returns the minimal element                       
                                                 return                                     (int)(                                     $x                                     + 1);                       
                         }                       
           
                         // Driver Code                       
                         $a                                     =                                     array                                     ( 3, 2, 1, 4 );                       
           
                         // computes the size of array                       
                         $n                                     = sizeof(                                     $a                                     );                       
           
                         // prints out the minimal element                       
                         echo                                     (findMin(                                     $a                                     ,                                     $n                                     ));                       
           
                         // This code is contributed by Ajit.                       
                         ?>                       

Javascript

                         <script>                       
                         // javascript Code to find Minimum element whose                       
                         // n-th power is greater than product of                       
                         // an array of size n                       
           
                                                 // function to find the minimum element                       
                                                 function                                     findMin(a, n)                       
                                                 {                       
                                   
                                                 // loop to traverse and store the                       
                                                 // sum of log                       
                                                 var                                     sum = 0;                       
                                                 for                                     (i = 0; i < n; i++)                       
           
                                                 // computes sum                       
                                                 sum += Math.log(a[i]);                       
           
                                                 // calculates the elements                       
                                                 // according to formula.                       
                                                 var                                     x = parseInt( Math.exp(sum / n));                       
           
                                                 // returns the minimal element                       
                                                 return                                     x + 1;                       
                                                 }                       
           
                                                 /* Driver program to test above function */                       
                                   
                                                 // initialised array                       
                                                 var                                     a = [ 3, 2, 1, 4 ];                       
           
                                                 // computes the size of array                       
                                                 var                                     n = a.length;                       
           
                                                 // prints out the minimal element                       
                                                 document.write(findMin(a, n));                       
           
                         // This code is contributed by aashish1995                       
                         </script>                       

输出：

时间复杂性： O（n*log（logn）） 辅助空间： O（1）本文由 拉贾·维克拉马蒂亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章