Un rompecabezas de array de productos | conjunto 3

Dada una array arr[] que consta de N enteros, la tarea es construir una array Producto del mismo tamaño sin usar el operador de división ( ‘/’ ) de modo que cada elemento de la array sea igual al producto de todos los elementos de arr[] excepto arr[yo] .

Ejemplos:

Entrada: arr[] = {10, 3, 5, 6, 2}
Salida: 180 600 360 300 900
Explicación:
3 * 5 * 6 * 2 es el producto de todos los elementos de la array excepto que 10 es 180
10 * 5 * 6 * 2 es el producto de todos los elementos del arreglo excepto 3 es 600.
10 * 3 * 6 * 2 es el producto de todos los elementos del arreglo excepto 5 es 360.
10 * 3 * 5 * 2 es el producto de todos los elementos del arreglo excepto 6 es 300 10 *
3 * 6 * 5 es el producto de todos los elementos del arreglo excepto que 2 es 9.

Entrada: arr[] = {1, 2, 1, 3, 4}
Salida: 24 12 24 8 6

Enfoque: La idea es usar las funciones log() y exp() en lugar de l og10() y pow(). A continuación se presentan algunas observaciones al respecto:

  • Supongamos que M es la multiplicación de todos los elementos del arreglo, entonces el elemento del arreglo de salida en la i -ésima posición será igual a M/arr[i].
  • Las divisiones de dos números se pueden realizar utilizando la propiedad del logaritmo y las funciones exp .
    • log(a) - log(b) = log(a/b)
    • exp(log(a/b)) = a/b
    • exp(log(a) - log(b)) = a/b
  • La función logarítmica no está definida para números menores que cero para mantener estos casos por separado.

Siga los pasos a continuación para resolver el problema:

  • Inicialice dos variables, digamos product = 1 y Z = 1 , para almacenar el producto de la array y el recuento de cero elementos.
  • Recorra la array y multiplique el producto por arr[i] si arr[i] no es igual a 0 . De lo contrario, incremente el recuento de Z en uno .
  • Recorra la array arr[] y realice lo siguiente:
    • Si Z es 1 y arr[i] no es cero, actualice arr[i] como arr[i] = 0 y continúe .
    • De lo contrario, si Z es 1 y arr[i] es 0 , actualice arr[i] como producto y continúe .
    • De lo contrario, si Z es mayor que 1 , asigne arr[i] como 0 y continúe.
    • Ahora encuentra el valor de abs(product)/abs(arr[i]) usando la fórmula discutida anteriormente y guárdalo en una variable, digamos curr .
    • Si el valor de arr[i] y el producto es negativo o si arr[i] y el producto son positivos, asigne arr[i] como curr .
    • De lo contrario, asigne arr[i] como -1*curr .
  • Después de completar los pasos anteriores, imprima la array arr[] .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to form product array
// with O(n) time and O(1) space
void productExceptSelf(int arr[],
                       int N)
{
    // Stores the product of array
    int product = 1;
 
    // Stores the count of zeros
    int z = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If arr[i] is not zero
        if (arr[i])
            product *= arr[i];
 
        // If arr[i] is zero then
        // increment count of z by 1
        z += (arr[i] == 0);
    }
 
    // Stores the absolute value
    // of the product
    int a = abs(product), b;
    for (int i = 0; i < N; i++) {
 
        // If Z is equal to 1
        if (z == 1) {
 
            // If arr[i] is not zero
            if (arr[i])
                arr[i] = 0;
 
            // Else
            else
                arr[i] = product;
            continue;
        }
 
        // If count of 0s at least 2
        else if (z > 1) {
 
            // Assign arr[i] = 0
            arr[i] = 0;
            continue;
        }
 
        // Store absolute value of arr[i]
        int b = abs(arr[i]);
 
        // Find the value of a/b
        int curr = round(exp(log(a) - log(b)));
 
        // If arr[i] and product both
        // are less than zero
        if (arr[i] < 0 && product < 0)
            arr[i] = curr;
 
        // If arr[i] and product both
        // are greater than zero
        else if (arr[i] > 0 && product > 0)
            arr[i] = curr;
 
        // Else
        else
            arr[i] = -1 * curr;
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 10, 3, 5, 6, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    productExceptSelf(arr, N);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to form product array
// with O(n) time and O(1) space
static void productExceptSelf(int arr[],
                       int N)
{
    // Stores the product of array
    int product = 1;
 
    // Stores the count of zeros
    int z = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If arr[i] is not zero
        if (arr[i] != 0)
            product *= arr[i];
 
        // If arr[i] is zero then
        // increment count of z by 1
        if (arr[i] == 0)
            z += 1;
    }
 
    // Stores the absolute value
    // of the product
    int a = Math.abs(product);
    for (int i = 0; i < N; i++) {
 
        // If Z is equal to 1
        if (z == 1) {
 
            // If arr[i] is not zero
            if (arr[i] != 0)
                arr[i] = 0;
 
            // Else
            else
                arr[i] = product;
            continue;
        }
 
        // If count of 0s at least 2
        else if (z > 1) {
 
            // Assign arr[i] = 0
            arr[i] = 0;
            continue;
        }
 
        // Store absolute value of arr[i]
        int b = Math.abs(arr[i]);
 
        // Find the value of a/b
        int curr = (int)Math.round(Math.exp(Math.log(a) - Math.log(b)));
 
        // If arr[i] and product both
        // are less than zero
        if (arr[i] < 0 && product < 0)
            arr[i] = curr;
 
        // If arr[i] and product both
        // are greater than zero
        else if (arr[i] > 0 && product > 0)
            arr[i] = curr;
 
        // Else
        else
            arr[i] = -1 * curr;
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
        System.out.print(arr[i] + " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = { 10, 3, 5, 6, 2 };
    int N = arr.length;
 
    // Function Call
    productExceptSelf(arr, N);
}
}
 
// This code is contributed by splevel62.

Python3

# Python 3 program for the above approach
import math
 
# Function to form product array
# with O(n) time and O(1) space
def productExceptSelf(arr, N) :
     
    # Stores the product of array
    product = 1
 
    # Stores the count of zeros
    z = 0
 
    # Traverse the array
    for i in range(N):
 
        # If arr[i] is not zero
        if (arr[i] != 0) :
            product *= arr[i]
 
        # If arr[i] is zero then
        # increment count of z by 1
        if(arr[i] == 0):
            z += 1
     
    # Stores the absolute value
    # of the product
    a = abs(product)
    for i in range(N):
 
        # If Z is equal to 1
        if (z == 1) :
 
            # If arr[i] is not zero
            if (arr[i] != 0) :
                arr[i] = 0
 
            # Else
            else :
                arr[i] = product
            continue
         
 
        # If count of 0s at least 2
        elif (z > 1) :
 
            # Assign arr[i] = 0
            arr[i] = 0
            continue
         
 
        # Store absolute value of arr[i]
        b = abs(arr[i])
 
        # Find the value of a/b
        curr = round(math.exp(math.log(a) - math.log(b)))
 
        # If arr[i] and product both
        # are less than zero
        if (arr[i] < 0 and product < 0):
            arr[i] = curr
 
        # If arr[i] and product both
        # are greater than zero
        elif (arr[i] > 0 and product > 0):
            arr[i] = curr
 
        # Else
        else:
            arr[i] = -1 * curr
     
    # Traverse the array arr[]
    for i in range(N):
        print(arr[i], end = " ")
     
# Driver Code
arr = [ 10, 3, 5, 6, 2 ]
N = len(arr)
 
# Function Call
productExceptSelf(arr, N)
 
# This code is contributed by code_hunt.

C#

// C# program for the above approach
using System;
class GFG
{
     
// Function to form product array
// with O(n) time and O(1) space
static void productExceptSelf(int[] arr,
                       int N)
{
    // Stores the product of array
    int product = 1;
 
    // Stores the count of zeros
    int z = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
        // If arr[i] is not zero
        if (arr[i] != 0)
            product *= arr[i];
 
        // If arr[i] is zero then
        // increment count of z by 1
        if (arr[i] == 0)
            z += 1;
    }
 
    // Stores the absolute value
    // of the product
    int a = Math.Abs(product);
    for (int i = 0; i < N; i++)
    {
 
        // If Z is equal to 1
        if (z == 1)
        {
 
            // If arr[i] is not zero
            if (arr[i] != 0)
                arr[i] = 0;
 
            // Else
            else
                arr[i] = product;
            continue;
        }
 
        // If count of 0s at least 2
        else if (z > 1)
        {
 
            // Assign arr[i] = 0
            arr[i] = 0;
            continue;
        }
 
        // Store absolute value of arr[i]
        int b = Math.Abs(arr[i]);
 
        // Find the value of a/b
        int curr = (int)Math.Round(Math.Exp(Math.Log(a) - Math.Log(b)));
 
        // If arr[i] and product both
        // are less than zero
        if (arr[i] < 0 && product < 0)
            arr[i] = curr;
 
        // If arr[i] and product both
        // are greater than zero
        else if (arr[i] > 0 && product > 0)
            arr[i] = curr;
 
        // Else
        else
            arr[i] = -1 * curr;
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++)
    {
        Console.Write(arr[i] + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int[] arr = { 10, 3, 5, 6, 2 };
    int N = arr.Length;
 
    // Function Call
    productExceptSelf(arr, N);
}
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
 
// Javascript Program to check matrix
// is scalar matrix or not.
 
 // Function to form product array
// with O(n) time and O(1) space
function productExceptSelf(arr,
                       N)
{
 
    // Stores the product of array
    let product = 1;
  
    // Stores the count of zeros
    let z = 0;
  
    // Traverse the array
    for (let i = 0; i < N; i++) {
  
        // If arr[i] is not zero
        if (arr[i] != 0)
            product *= arr[i];
  
        // If arr[i] is zero then
        // increment count of z by 1
        if (arr[i] == 0)
            z += 1;
    }
  
    // Stores the absolute value
    // of the product
    let a = Math.abs(product);
    for (let i = 0; i < N; i++) {
  
        // If Z is equal to 1
        if (z == 1) {
  
            // If arr[i] is not zero
            if (arr[i] != 0)
                arr[i] = 0;
  
            // Else
            else
                arr[i] = product;
            continue;
        }
  
        // If count of 0s at least 2
        else if (z > 1) {
  
            // Assign arr[i] = 0
            arr[i] = 0;
            continue;
        }
  
        // Store absolute value of arr[i]
        let b = Math.abs(arr[i]);
  
        // Find the value of a/b
        let curr = Math.round(Math.exp(Math.log(a) - Math.log(b)));
  
        // If arr[i] and product both
        // are less than zero
        if (arr[i] < 0 && product < 0)
            arr[i] = curr;
  
        // If arr[i] and product both
        // are greater than zero
        else if (arr[i] > 0 && product > 0)
            arr[i] = curr;
  
        // Else
        else
            arr[i] = -1 * curr;
    }
  
    // Traverse the array arr[]
    for (let i = 0; i < N; i++) {
        document.write(arr[i] + " ");
    }
}
      
    // Driver Code
    let arr = [ 10, 3, 5, 6, 2 ];
    let N = arr.length;
  
    // Function Call
    productExceptSelf(arr, N);
 
// This code is contributed by souravghosh0416.
</script>
Producción: 

180 600 360 300 900

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoques alternativos: consulte las publicaciones anteriores de este artículo para obtener enfoques alternativos:

Publicación traducida automáticamente

Artículo escrito por avamsikrishnaavk y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *