Un rompecabezas de gama de productos | Juego 2 (O(1) Espacio)

Dada una array arr[] de n enteros, construya una array de productos prod[] (del mismo tamaño) tal que prod[i] sea igual al producto de todos los elementos de arr[] excepto arr[i]. Resuélvelo sin operador de división y en O(n).

Ejemplo: 

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}

Ya hay un enfoque O(n) discutido en Un rompecabezas de array de productos | conjunto 1 . El enfoque anterior utiliza espacio adicional O(n) para construir una array de productos.

Solución 1: usar la propiedad de registro. 

Enfoque: en esta publicación, se ha discutido un mejor enfoque que utiliza la propiedad de registro para encontrar el producto de todos los elementos de la array, excepto en un índice particular. Este enfoque no utiliza espacio adicional.

Usar la propiedad de log para multiplicar números grandes  

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))

Entonces, la idea es simple,  
recorre la array y encuentra la suma del registro de todos los elementos,   

log(a[0]) + log(a[1]) + 
.. + log(a[n-1])

Luego, recorra nuevamente la array y encuentre el producto usando esta fórmula.  

antilog((log(a[0]) + log(a[1]) +
 .. + log(a[n-1])) - log(a[i]))

Esto es igual al producto de todos los elementos excepto a[i], es decir, antilog(sum-log(a[i])). 

Implementación:

// 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;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// C program for product array puzzle
// with O(n) time and O(1) space.
#include <stdio.h>
#include <math.h>
 
// 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++)
        printf("%d ",(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]);
    printf("The product array is: \n");
    productPuzzle(a, n);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// 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 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# 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 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
?>

<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

Análisis de Complejidad: 

• Complejidad temporal: O(n). 
  Solo se requieren dos recorridos de la array.
• Complejidad espacial: O(1). 
  No se requiere espacio adicional.

Enfoque alternativo: aquí hay otro enfoque para resolver el problema anterior mediante el uso de la función pow(), no usa división y funciona en tiempo O(n). 
Recorre la array y encuentra el producto de todos los elementos de la array. Almacenar el producto en una variable. 

Luego, nuevamente recorra la array y encuentre el producto de todos los elementos excepto ese número usando la fórmula (producto * pow (a [i], -1)) 

Implementación:

// 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 Aditya Kumar (adityakumar129)

// C program for product array puzzle
// with O(n) time and O(1) space.
#include <math.h>
#include <stdio.h>
 
// 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++)
        printf("%d ", (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 Aditya Kumar (adityakumar129)

// 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

# 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# 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

<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

 Análisis de Complejidad: 

• Complejidad de tiempo: O (n), solo se requieren dos recorridos de la array.
• Complejidad del espacio: O(1),  No se requiere espacio adicional.

Nota: Este enfoque asume que los elementos de la array no son 0.
Este enfoque lo proporciona Sitesh Roy . 

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.