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