# 算法设计：解决乘积数组问题|S2 (使用O(1)空间)

2021年3月28日15:37:28 发表评论 365 次浏览

## 本文概述

``````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}``````

``````x = a * b * c * d
log(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(a[0]) + log(a[1]) +
.. + log(a[n-1])``````

``````antilog((log(a[0]) + log(a[1]) +
.. + log(a[n-1])) - 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: \n" ;
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``````

## python

``````# 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])))), 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: \n" ;
productPuzzle( \$a , \$n );

// This code is contributed by mits
?>``````

``````The product array is:
180 600 360 300 900``````

• 时间复杂度：O(n)。
仅需要两次遍历数组。
• 空间复杂度：O(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 << prod * ( int ) 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``````

``180 600 360 300 900``

• 时间复杂度：O(n)。
仅需要两次遍历数组。
• 空间复杂度：O(1)。
不需要额外的空间。