给定一个由n个整数组成的数组arr[]，构造一个乘积数组prod[]（大小相同），使prod[i]等于除arr[i]之外的所有arr[]元素的乘积。解决它 无除法运算符 在O（n）中。 例子：
null
Input: arr[] = {10, 3, 5, 6, 2}Output: prod[] = {180, 600, 360, 300, 900}The elements of output array are {3*5*6*2, 10*5*6*2, 10*3*6*2, 10*3*5*2, 10*3*5*6}Input: arr[] = {1, 2, 1, 3, 4}Output: prod[] = {24, 12, 24, 8, 6}The elements of output array are {3*4*1*2, 1*1*3*4, 4*3*2*1, 1*1*4*2, 1*1*3*2}
在本文中已经讨论了O（n）方法 产品阵列难题|集1 前一种方法使用额外的O（n）空间来构造产品数组。 解决方案1： 使用日志属性。 方法： 在本文中，我们讨论了一种更好的方法，它使用log属性来查找数组中除特定索引外的所有元素的乘积。这种方法不需要额外的空间。 使用log属性将大数相乘
x = a * b * c * dlog(x) = log(a * b * c * d)log(x) = log(a) + log(b) + log(c) + log(d)x = antilog(log(a) + log(b) + log(c) + log(d))
所以这个想法很简单， 遍历数组并找到所有元素的log之和，
log(a[0]) + log(a[1]) + .. + log(a[n-1])
然后再次遍历数组，用这个公式找到乘积。
antilog((log(a[0]) + log(a[1]) + .. + log(a[n-1])) - log(a[i]))
这等于除a[i]之外的所有元素的乘积，即反对数（sum-log（a[i]）。
C++
// C++ program for product array puzzle // with O(n) time and O(1) space. #include <bits/stdc++.h> using namespace std; // epsilon value to maintain precision #define EPS 1e-9 void productPuzzle( int a[], int n) { // to hold sum of all values long double sum = 0; for ( int i = 0; i < n; i++) sum += ( long double ) log10 (a[i]); // output product for each index // antilog to find original product value for ( int i = 0; i < n; i++) cout << ( int )(EPS + pow (( long double )10.00, sum - log10 (a[i]))) << " " ; } // Driver code int main() { int a[] = { 10, 3, 5, 6, 2 }; int n = sizeof (a) / sizeof (a[0]); cout << "The product array is: " ; productPuzzle(a, n); return 0; } |
JAVA
// Java program for product array puzzle // with O(n) time and O(1) space. public class Array_puzzle_2 { // epsilon value to maintain precision static final double EPS = 1e- 9 ; static void productPuzzle( int a[], int n) { // to hold sum of all values double sum = 0 ; for ( int i = 0 ; i < n; i++) sum += Math.log10(a[i]); // output product for each index // anti log to find original product value for ( int i = 0 ; i < n; i++) System.out.print( ( int )(EPS + Math.pow( 10.00 , sum - Math.log10(a[i]))) + " " ); } // Driver code public static void main(String args[]) { int a[] = { 10 , 3 , 5 , 6 , 2 }; int n = a.length; System.out.println( "The product array is: " ); productPuzzle(a, n); } } // This code is contributed by Sumit Ghosh |
Python3
# Python program for product array puzzle # with O(n) time and O(1) space. import math # epsilon value to maintain precision EPS = 1e - 9 def productPuzzle(a, n): # to hold sum of all values sum = 0 for i in range (n): sum + = math.log10(a[i]) # output product for each index # antilog to find original product value for i in range (n): print ( int ((EPS + pow ( 10.00 , sum - math.log10(a[i])))),end = " " ) return # Driver code a = [ 10 , 3 , 5 , 6 , 2 ] n = len (a) print ( "The product array is: " ) productPuzzle(a, n) # This code is contributed by Sachin Bisht |
C#
// C# program for product // array puzzle with O(n) // time and O(1) space. using System; class GFG { // epsilon value to // maintain precision static double EPS = 1e-9; static void productPuzzle( int [] a, int n) { // to hold sum of all values double sum = 0; for ( int i = 0; i < n; i++) sum += Math.Log10(a[i]); // output product for each // index anti log to find // original product value for ( int i = 0; i < n; i++) Console.Write(( int )(EPS + Math.Pow(10.00, sum - Math.Log10(a[i]))) + " " ); } // Driver code public static void Main() { int [] a = { 10, 3, 5, 6, 2 }; int n = a.Length; Console.WriteLine( "The product array is: " ); productPuzzle(a, n); } } // This code is contributed by mits |
PHP
<?php // PHP program for product array puzzle // with O(n) time and O(1) space. // epsilon value to maintain precision $EPS =1e-9; function productPuzzle( $a , $n ) { global $EPS ; // to hold sum of all values $sum = 0; for ( $i = 0; $i < $n ; $i ++) $sum += (double)log10( $a [ $i ]); // output product for each index // antilog to find original product value for ( $i = 0; $i < $n ; $i ++) echo (int)( $EPS + pow((double)10.00, $sum - log10( $a [ $i ]))). " " ; } // Driver code $a = array (10, 3, 5, 6, 2 ); $n = count ( $a ); echo "The product array is: " ; productPuzzle( $a , $n ); // This code is contributed by mits ?> |
Javascript
<script> // javascript program for product array puzzle // with O(n) time and O(1) space. // epsilon value to maintain precision var EPS = 1e-9; function productPuzzle(a , n) { // to hold sum of all values var sum = 0; for ( var i = 0; i < n; i++) sum += Math.log10(a[i]); // output product for each index // anti log to find original product value for ( var i = 0; i < n; i++) document.write( parseInt((EPS + Math.pow( 10.00, sum - Math.log10(a[i])))) + " " ); } // Driver code var a = [ 10, 3, 5, 6, 2 ]; var n = a.length; document.write( "The product array is: " ); productPuzzle(a, n); // This code is contributed by 29AjayKumar </script> |
输出：
The product array is: 180 600 360 300 900
复杂性分析：
- 时间复杂性： O（n）。 只需要对数组进行两次遍历。
- 空间复杂性： O（1）。 不需要额外的空间。
这种方法是由阿披实·拉吉普特提出的。 替代方法： 下面是另一种通过使用pow（）函数来解决上述问题的方法，它不使用除法，在O（n）时间内工作。 遍历数组并找到数组中所有元素的乘积。将产品存储在变量中。 然后再次遍历数组，使用公式（乘积*pow（a[i]，-1]）找到除该数字之外的所有元素的乘积
C++
// C++ program for product array puzzle // with O(n) time and O(1) space. #include <bits/stdc++.h> using namespace std; // Solve function which prints the answer void solve( int arr[], int n) { // Initialize a variable to store the // total product of the array elements int prod = 1; for ( int i = 0; i < n; i++) prod *= arr[i]; // we know x/y mathematically is same // as x*(y to power -1) for ( int i = 0; i < n; i++) { cout << ( int )(prod * pow (arr[i], -1)) << ' ' ; } } // Driver Code int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof (arr) / sizeof (arr[0]); solve(arr, n); return 0; } // This code is contributed by Sitesh Roy |
JAVA
// Java program for product array puzzle // with O(n) time and O(1) space. public class ArrayPuzzle { static void solve( int arr[], int n) { // Initialize a variable to store the // total product of the array elements int prod = 1 ; for ( int i = 0 ; i < n; i++) prod *= arr[i]; // we know x/y mathematically is same // as x*(y to power -1) for ( int i = 0 ; i < n; i++) System.out.print( ( int )prod * Math.pow(arr[i], - 1 ) + " " ); } // Driver code public static void main(String args[]) { int arr[] = { 10 , 3 , 5 , 6 , 2 }; int n = arr.length; solve(arr, n); } } // This code is contributed by Sitesh Roy |
Python3
# Python program for product array puzzle # with O(n) time and O(1) space. def solve(arr, n): # Initialize a variable to store the # total product of the array elements prod = 1 for i in arr: prod * = i # we know x / y mathematically is same # as x*(y to power -1) for i in arr: print ( int (prod * (i * * - 1 )), end = " " ) # Driver Code arr = [ 10 , 3 , 5 , 6 , 2 ] n = len (arr) solve(arr, n) # This code is contributed by Sitesh Roy |
C#
// C# program for product array puzzle // with O(n) time and O(1) space. using System; class GFG { public class ArrayPuzzle { static void solve( int [] arr, int n) { // Initialize a variable to store the // total product of the array elements int prod = 1; for ( int i = 0; i < n; i++) prod *= arr[i]; // we know x/y mathematically is same // as x*(y to power -1) for ( int i = 0; i < n; i++) Console.Write( ( int )prod * Math.Pow(arr[i], -1) + " " ); } // Driver code static public void Main() { int [] arr = { 10, 3, 5, 6, 2 }; int n = arr.Length; solve(arr, n); } } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program for product array puzzle // with O(n) time and O(1) space. function solve(arr, n) { // Initialize a variable to store the // total product of the array elements let prod = 1; for (let i = 0; i < n; i++) prod *= arr[i]; // we know x/y mathematically is same // as x*(y to power -1) for (let i = 0; i < n; i++) document.write( prod * Math.pow(arr[i], -1) + " " ); } // Driver program let arr = [10, 3, 5, 6, 2 ]; let n = arr.length; solve(arr, n); // This code is contributed by code_hunt. </script> |
输出：
180 600 360 300 900
复杂性分析：
- 时间复杂性： O（n）。 只需要对数组进行两次遍历。
- 空间复杂性： O（1）。 不需要额外的空间。
注意：这种方法假设数组元素不是0。 这种方法由 斯泰什·罗伊 . 如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
