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 en tiempo O(n) .
Ejemplo :
Input: arr[] = {10, 3, 5, 6, 2}
Output: prod[] = {180, 600, 360, 300, 900}
3 * 5 * 6 * 2 product of other array
elements except 10 is 180
10 * 5 * 6 * 2 product of other array
elements except 3 is 600
10 * 3 * 6 * 2 product of other array
elements except 5 is 360
10 * 3 * 5 * 2 product of other array
elements except 6 is 300
10 * 3 * 6 * 5 product of other array
elements except 2 is 900
Input: arr[] = {1, 2, 3, 4, 5}
Output: prod[] = {120, 60, 40, 30, 24 }
2 * 3 * 4 * 5 product of other array
elements except 1 is 120
1 * 3 * 4 * 5 product of other array
elements except 2 is 60
1 * 2 * 4 * 5 product of other array
elements except 3 is 40
1 * 2 * 3 * 5 product of other array
elements except 4 is 30
1 * 2 * 3 * 4 product of other array
elements except 5 is 24
Solución ingenua:
enfoque: cree dos espacios adicionales, es decir, dos arrays adicionales para almacenar el producto de todos los elementos de la array desde el inicio hasta ese índice y otra array para almacenar el producto de todos los elementos de la array desde el final de la array hasta ese índice.
Para obtener el producto excluyendo ese índice, multiplique el prefijo producto hasta el índice i-1 con el sufijo producto hasta el índice i+1.
Algoritmo:
- Cree dos prefijos y sufijos de array de longitud n , es decir, longitud de la array original, inicialice prefijo [0] = 1 y sufijo [n-1] = 1 y también otra array para almacenar el producto.
- Atraviesa la array desde el segundo índice hasta el final.
- Para cada índice , actualizo el prefijo [i] como prefijo [i] = prefijo [i-1] * array [i-1] , es decir, almaceno el producto hasta el índice i-1 desde el inicio de la array.
- Atraviesa la array desde el penúltimo índice hasta el comienzo.
- Para cada índice , actualizo el sufijo [i] como sufijo [i] = sufijo [i+1] * array [i+1] , es decir, almacene el producto hasta el índice i+1 desde el final de la array
- Atraviesa la array de principio a fin.
- Para cada índice i, la salida será prefix[i] * suffix[i] , el producto del elemento del arreglo excepto ese elemento.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
/* Function to print product array
for a given array arr[] of size n */
void productArray(int arr[], int n)
{
// Base case
if (n == 1) {
cout << 0;
return;
}
/* Allocate memory for temporary
arrays left[] and right[] */
int* left = new int[sizeof(int) * n];
int* right = new int[sizeof(int) * n];
/* Allocate memory for the product array */
int* prod = new int[sizeof(int) * n];
int i, j;
/* Left most element of left
array is always 1 */
left[0] = 1;
/* Right most element of right
array is always 1 */
right[n - 1] = 1;
/* Construct the left array */
for (i = 1; i < n; i++)
left[i] = arr[i - 1] * left[i - 1];
/* Construct the right array */
for (j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] * right[j + 1];
/* Construct the product array using
left[] and right[] */
for (i = 0; i < n; i++)
prod[i] = left[i] * right[i];
/* print the constructed prod array */
for (i = 0; i < n; i++)
cout << prod[i] << " ";
return;
}
/* Driver code*/
int main()
{
int arr[] = { 10, 3, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The product array is: \n";
productArray(arr, n);
}
// This is code is contributed by rathbhupendra
C
#include <stdio.h>
#include <stdlib.h>
/* Function to print product array
for a given array arr[] of size n */
void productArray(int arr[], int n)
{
// Base case
if (n == 1) {
printf("0");
return;
}
/* Allocate memory for temporary
arrays left[] and right[] */
int* left = (int*)malloc(sizeof(int) * n);
int* right = (int*)malloc(sizeof(int) * n);
/* Allocate memory for the product array */
int* prod = (int*)malloc(sizeof(int) * n);
int i, j;
/* Left most element of left array
is always 1 */
left[0] = 1;
/* Right most element of right
array is always 1 */
right[n - 1] = 1;
/* Construct the left array */
for (i = 1; i < n; i++)
left[i] = arr[i - 1] * left[i - 1];
/* Construct the right array */
for (j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] * right[j + 1];
/* Construct the product array using
left[] and right[] */
for (i = 0; i < n; i++)
prod[i] = left[i] * right[i];
/* print the constructed prod array */
for (i = 0; i < n; i++)
printf("%d ", prod[i]);
return;
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 10, 3, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("The product array is: \n");
productArray(arr, n);
getchar();
}
Java
class ProductArray {
/* Function to print product array
for a given array arr[] of size n */
void productArray(int arr[], int n)
{
// Base case
if (n == 1) {
System.out.print(0);
return;
}
// Initialize memory to all arrays
int left[] = new int[n];
int right[] = new int[n];
int prod[] = new int[n];
int i, j;
/* Left most element of left array
is always 1 */
left[0] = 1;
/* Right most element of right
array is always 1 */
right[n - 1] = 1;
/* Construct the left array */
for (i = 1; i < n; i++)
left[i] = arr[i - 1] * left[i - 1];
/* Construct the right array */
for (j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] * right[j + 1];
/* Construct the product array using
left[] and right[] */
for (i = 0; i < n; i++)
prod[i] = left[i] * right[i];
/* print the constructed prod array */
for (i = 0; i < n; i++)
System.out.print(prod[i] + " ");
return;
}
/* Driver program to test the above function */
public static void main(String[] args)
{
ProductArray pa = new ProductArray();
int arr[] = { 10, 3, 5, 6, 2 };
int n = arr.length;
System.out.println("The product array is : ");
pa.productArray(arr, n);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python implementation of the above approach
# Function to print product array for a given array
# arr[] of size n
def productArray(arr, n):
# Base case
if(n == 1):
print(0)
return
# Allocate memory for temporary arrays left[] and right[]
left = [0]*n
right = [0]*n
# Allocate memory for the product array
prod = [0]*n
# Left most element of left array is always 1
left[0] = 1
# Right most element of right array is always 1
right[n - 1] = 1
# Construct the left array
for i in range(1, n):
left[i] = arr[i - 1] * left[i - 1]
# Construct the right array
for j in range(n-2, -1, -1):
right[j] = arr[j + 1] * right[j + 1]
# Construct the product array using
# left[] and right[]
for i in range(n):
prod[i] = left[i] * right[i]
# print the constructed prod array
for i in range(n):
print(prod[i], end=' ')
# Driver code
arr = [10, 3, 5, 6, 2]
n = len(arr)
print("The product array is:")
productArray(arr, n)
# This code is contributed by ankush_953
C#
using System;
class GFG {
/* Function to print product array
for a given array arr[] of size n */
static void productArray(int[] arr, int n)
{
// Base case
if (n == 1) {
Console.Write(0);
return;
}
// Initialize memory to all arrays
int[] left = new int[n];
int[] right = new int[n];
int[] prod = new int[n];
int i, j;
/* Left most element of left array
is always 1 */
left[0] = 1;
/* Right most element of right
array is always 1 */
right[n - 1] = 1;
/* Construct the left array */
for (i = 1; i < n; i++)
left[i] = arr[i - 1] * left[i - 1];
/* Construct the right array */
for (j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] * right[j + 1];
/* Construct the product array using
left[] and right[] */
for (i = 0; i < n; i++)
prod[i] = left[i] * right[i];
/* print the constructed prod array */
for (i = 0; i < n; i++)
Console.Write(prod[i] + " ");
return;
}
/* Driver program to test the above function */
public static void Main()
{
int[] arr = { 10, 3, 5, 6, 2 };
int n = arr.Length;
Console.Write("The product array is :\n");
productArray(arr, n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// Function to print product
// array for a given array
// arr[] of size n
function productArray($arr, $n)
{
// Base case
if($n == 1) {
echo "0";
return;
}
// Initialize memory
// to all arrays
$left = array();
$right = array();
$prod = array();
$i; $j;
// Left most element of
// left array is always 1
$left[0] = 1;
// Right most element of
// right array is always 1
$right[$n - 1] = 1;
// Construct the left array
for ($i = 1; $i < $n; $i++)
$left[$i] = $arr[$i - 1] *
$left[$i - 1];
// Construct the right array
for ($j = $n - 2; $j >= 0; $j--)
$right[$j] = $arr[$j + 1] *
$right[$j + 1];
// Construct the product array
// using left[] and right[]
for ($i = 0; $i < $n; $i++)
$prod[$i] = $left[$i] *
$right[$i];
// print the constructed prod array
for ($i = 0; $i < $n; $i++)
echo $prod[$i], " ";
return;
}
// Driver Code
$arr = array(10, 3, 5, 6, 2);
$n = count($arr);
echo "The product array is : \n";
productArray($arr, $n);
// This code has been contributed by anuj_67.
?>
Javascript
<script>
/* Function to print product array
for a given array arr[] of size n */
function productArray(arr, n)
{
// Base case
if (n == 1) {
document.write(0);
return;
}
// Initialize memory to all arrays
let left = new Array(n);
let right = new Array(n);
let prod = new Array(n);
let i, j;
/* Left most element of left array
is always 1 */
left[0] = 1;
/* Right most element of right
array is always 1 */
right[n - 1] = 1;
/* Construct the left array */
for (i = 1; i < n; i++)
left[i] = arr[i - 1] * left[i - 1];
/* Construct the right array */
for (j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] * right[j + 1];
/* Construct the product array using
left[] and right[] */
for (i = 0; i < n; i++)
prod[i] = left[i] * right[i];
/* print the constructed prod array */
for (i = 0; i < n; i++)
document.write(prod[i] + " ");
return;
}
// Driver code
let arr = [ 10, 3, 5, 6, 2 ];
let n = arr.length;
document.write("The product array is :" + "</br>");
productArray(arr, n);
// This code is contributed by mukesh07.
</script>
Producción
The product array is: 180 600 360 300 900
Análisis de Complejidad:
- Complejidad temporal: O(n).
La array debe recorrerse tres veces, por lo que la complejidad del tiempo es O (n). - Complejidad espacial: O(n).
Se necesitan dos arrays adicionales y una array para almacenar la salida, por lo que la complejidad del espacio es O (n)
Nota: El método anterior se puede optimizar para trabajar en la complejidad espacial O(1). Gracias a Dileep por sugerir la siguiente solución.
Solución eficiente:
Enfoque: en la solución anterior, se crearon dos arrays adicionales para almacenar el prefijo y el sufijo, en esta solución, almacene el producto del prefijo y el sufijo en la array de salida (o array de productos) en sí. Reduciendo así el espacio requerido.
Algoritmo:
- Cree un producto de array e inicialice su valor en 1 y una variable temp = 1.
- Atraviesa la array de principio a fin.
- Para cada índice , actualizo el producto [i] como producto [i] = temp y temp = temp * array [i] , es decir, almaceno el producto hasta el índice i-1 desde el inicio de la array.
- inicialice temp = 1 y recorra la array desde el último índice hasta el comienzo.
- Para cada índice actualizo product[i] como product[i] = product[i] * temp y temp = temp * array[i] , es decir, multiplique con el producto hasta el índice i+1 desde el final de la array.
- Imprima la array de productos.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
/* Function to print product array
for a given array arr[] of size n */
void productArray(int arr[], int n)
{
// Base case
if (n == 1) {
cout << 0;
return;
}
int i, temp = 1;
/* Allocate memory for the product array */
int* prod = new int[(sizeof(int) * n)];
/* Initialize the product array as 1 */
memset(prod, 1, n);
/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for (i = 0; i < n; i++) {
prod[i] = temp;
temp *= arr[i];
}
/* Initialize temp to 1
for product on right side */
temp = 1;
/* In this loop, temp variable contains product of
elements on right side excluding arr[i] */
for (i = n - 1; i >= 0; i--) {
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i = 0; i < n; i++)
cout << prod[i] << " ";
return;
}
// Driver Code
int main()
{
int arr[] = { 10, 3, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The product array is: \n";
productArray(arr, n);
}
// This code is contributed by rathbhupendra
Java
class ProductArray {
void productArray(int arr[], int n)
{
// Base case
if (n == 1) {
System.out.print("0");
return;
}
int i, temp = 1;
/* Allocate memory for the product array */
int prod[] = new int[n];
/* Initialize the product array as 1 */
for (int j = 0; j < n; j++)
prod[j] = 1;
/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for (i = 0; i < n; i++) {
prod[i] = temp;
temp *= arr[i];
}
/* Initialize temp to 1 for product on right side */
temp = 1;
/* In this loop, temp variable contains product of
elements on right side excluding arr[i] */
for (i = n - 1; i >= 0; i--) {
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i = 0; i < n; i++)
System.out.print(prod[i] + " ");
return;
}
/* Driver program to test above functions */
public static void main(String[] args)
{
ProductArray pa = new ProductArray();
int arr[] = { 10, 3, 5, 6, 2 };
int n = arr.length;
System.out.println("The product array is : ");
pa.productArray(arr, n);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python3 program for A Product Array Puzzle
def productArray(arr, n):
# Base case
if n == 1:
print(0)
return
i, temp = 1, 1
# Allocate memory for the product array
prod = [1 for i in range(n)]
# Initialize the product array as 1
# In this loop, temp variable contains product of
# elements on left side excluding arr[i]
for i in range(n):
prod[i] = temp
temp *= arr[i]
# Initialize temp to 1 for product on right side
temp = 1
# In this loop, temp variable contains product of
# elements on right side excluding arr[i]
for i in range(n - 1, -1, -1):
prod[i] *= temp
temp *= arr[i]
# Print the constructed prod array
for i in range(n):
print(prod[i], end=" ")
return
# Driver Code
arr = [10, 3, 5, 6, 2]
n = len(arr)
print("The product array is: n")
productArray(arr, n)
# This code is contributed by mohit kumar
C#
using System;
class GFG {
static void productArray(int[] arr, int n)
{
// Base case
if (n == 1) {
Console.Write(0);
return;
}
int i, temp = 1;
/* Allocate memory for the product
array */
int[] prod = new int[n];
/* Initialize the product array as 1 */
for (int j = 0; j < n; j++)
prod[j] = 1;
/* In this loop, temp variable contains
product of elements on left side
excluding arr[i] */
for (i = 0; i < n; i++) {
prod[i] = temp;
temp *= arr[i];
}
/* Initialize temp to 1 for product on
right side */
temp = 1;
/* In this loop, temp variable contains
product of elements on right side
excluding arr[i] */
for (i = n - 1; i >= 0; i--) {
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i = 0; i < n; i++)
Console.Write(prod[i] + " ");
return;
}
/* Driver program to test above functions */
public static void Main()
{
int[] arr = { 10, 3, 5, 6, 2 };
int n = arr.Length;
Console.WriteLine("The product array is : ");
productArray(arr, n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program for
// A Product Array Puzzle
function productArray($arr, $n)
{
// Base case
if ($n == 1) {
echo "0";
return;
}
$i; $temp = 1;
/* Allocate memory for
the productarray */
$prod = array();
/* Initialize the product
array as 1 */
for( $j = 0; $j < $n; $j++)
$prod[$j] = 1;
/* In this loop, temp
variable contains
product of elements
on left side
excluding arr[i] */
for ($i = 0; $i < $n; $i++)
{
$prod[$i] = $temp;
$temp *= $arr[$i];
}
/* Initialize temp to 1
for product on right
side */
$temp = 1;
/* In this loop, temp
variable contains
product of elements
on right side
excluding arr[i] */
for ($i = $n - 1; $i >= 0; $i--)
{
$prod[$i] *= $temp;
$temp *= $arr[$i];
}
/* print the constructed
prod array */
for ($i = 0; $i < $n; $i++)
echo $prod[$i], " ";
return;
}
// Driver Code
$arr = array(10, 3, 5, 6, 2);
$n = count($arr);
echo "The product array is : \n";
productArray($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
function productArray(arr , n)
{
// Base case
if (n == 1) {
document.write("0");
return;
}
var i, temp = 1;
/* Allocate memory for the product array */
var prod = Array(n).fill(0);
/* Initialize the product array as 1 */
for (j = 0; j < n; j++)
prod[j] = 1;
/*
In this loop, temp variable contains
product of elements on left side
excluding arr[i]
*/
for (i = 0; i < n; i++) {
prod[i] = temp;
temp *= arr[i];
}
/* Initialize temp to 1 for
product on right side */
temp = 1;
/*
In this loop, temp variable contains
product of elements on right side
excluding arr[i]
*/
for (i = n - 1; i >= 0; i--) {
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i = 0; i < n; i++)
document.write(prod[i] + " ");
return;
}
/* Driver program to test above functions */
var arr = [ 10, 3, 5, 6, 2 ];
var n = arr.length;
document.write("The product array is : ");
productArray(arr, n);
// This code contributed by Rajput-Ji
</script>
Producción
The product array is: 180 600 360 300 900
Análisis de Complejidad:
- Complejidad temporal: O(n).
La array original debe recorrerse solo una vez, por lo que la complejidad del tiempo es constante. - Complejidad espacial: O(n).
Aunque se eliminan las arrays adicionales, la complejidad del espacio sigue siendo O(n), ya que aún se necesita la array del producto.
Otro enfoque:
Almacene el producto de todos los elementos en una variable y luego itere la array y agregue product/current_index_value en una nueva array. y luego devolver esta nueva array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
long* productExceptSelf(int a[], int n)
{
long prod = 1;
long flag = 0;
// product of all elements
for (int i = 0; i < n; i++) {
// counting number of elements
// which have value
// 0
if (a[i] == 0)
flag++;
else
prod *= a[i];
}
// creating a new array of size n
long* arr = new long[n];
for (int i = 0; i < n; i++) {
// if number of elements in
// array with value 0
// is more than 1 than each
// value in new array
// will be equal to 0
if (flag > 1) {
arr[i] = 0;
}
// if no element having value
// 0 than we will
// insert product/a[i] in new array
else if (flag == 0)
arr[i] = (prod / a[i]);
// if 1 element of array having
// value 0 than all
// the elements except that index
// value , will be
// equal to 0
else if (flag == 1 && a[i] != 0) {
arr[i] = 0;
}
// if(flag == 1 && a[i] == 0)
else
arr[i] = prod;
}
return arr;
}
// Driver Code
int main()
{
int n = 5;
int array[] = { 10, 3, 5, 6, 2 };
long* ans;
ans = productExceptSelf(array, n);
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
// cout<<"GFG!";
return 0;
}
// This code is contributed by RohitOberoi.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class Solution {
public static long[] productExceptSelf(int a[], int n)
{
long prod = 1;
long flag = 0;
// product of all elements
for (int i = 0; i < n; i++) {
// counting number of elements
// which have value
// 0
if (a[i] == 0)
flag++;
else
prod *= a[i];
}
// creating a new array of size n
long arr[] = new long[n];
for (int i = 0; i < n; i++) {
// if number of elements in
// array with value 0
// is more than 1 than each
// value in new array
// will be equal to 0
if (flag > 1) {
arr[i] = 0;
}
// if no element having value
// 0 than we will
// insert product/a[i] in new array
else if (flag == 0)
arr[i] = (prod / a[i]);
// if 1 element of array having
// value 0 than all
// the elements except that index
// value , will be
// equal to 0
else if (flag == 1 && a[i] != 0) {
arr[i] = 0;
}
// if(flag == 1 && a[i] == 0)
else
arr[i] = prod;
}
return arr;
}
// Driver Code
public static void main(String args[])
throws IOException
{
int n = 5;
int[] array = { 10, 3, 5, 6, 2 };
Solution ob = new Solution();
long[] ans = new long[n];
ans = ob.productExceptSelf(array, n);
for (int i = 0; i < n; i++) {
System.out.print(ans[i] + " ");
}
}
}
// This code is contributed by Kapil Kumar (kapilkumar2001)
Python3
# Python3 program for the above approach def productExceptSelf(a, n): prod = 1 flag = 0 for i in range(n): # Counting number of elements # which have value # 0 if (a[i] == 0): flag += 1 else: prod *= a[i] # Creating a new array of size n arr = [0 for i in range(n)] for i in range(n): # If number of elements in # array with value 0 # is more than 1 than each # value in new array # will be equal to 0 if (flag > 1): arr[i] = 0 # If no element having value # 0 than we will # insert product/a[i] in new array elif (flag == 0): arr[i] = (prod // a[i]) # If 1 element of array having # value 0 than all # the elements except that index # value , will be # equal to 0 elif (flag == 1 and a[i] != 0): arr[i] = 0 # If(flag == 1 && a[i] == 0) else: arr[i] = prod return arr # Driver Code n = 5 array = [10, 3, 5, 6, 2] ans = productExceptSelf(array, n) print(*ans) # This code is contributed by rag2127
C#
using System;
public class GFG {
public static long[] productExceptSelf(int[] a, int n)
{
long prod = 1;
long flag = 0;
// product of all elements
for (int i = 0; i < n; i++) {
// counting number of elements
// which have value
// 0
if (a[i] == 0)
flag++;
else
prod *= a[i];
}
// creating a new array of size n
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
// if number of elements in
// array with value 0
// is more than 1 than each
// value in new array
// will be equal to 0
if (flag > 1) {
arr[i] = 0;
}
// if no element having value
// 0 than we will
// insert product/a[i] in new array
else if (flag == 0)
arr[i] = (prod / a[i]);
// if 1 element of array having
// value 0 than all
// the elements except that index
// value , will be
// equal to 0
else if (flag == 1 && a[i] != 0) {
arr[i] = 0;
}
// if(flag == 1 && a[i] == 0)
else
arr[i] = prod;
}
return arr;
}
// Driver Code
static public void Main()
{
int n = 5;
int[] array = { 10, 3, 5, 6, 2 };
long[] ans = new long[n];
ans = productExceptSelf(array, n);
for (int i = 0; i < n; i++) {
Console.Write(ans[i] + " ");
}
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program for the above approach
function productExceptSelf(a, n)
{
let prod = 1;
let flag = 0;
// Product of all elements
for(let i = 0; i < n; i++)
{
// Counting number of elements
// which have value
// 0
if (a[i] == 0)
flag++;
else
prod *= a[i];
}
// Creating a new array of size n
let arr = Array(n).fill(0);
for(let i = 0; i < n; i++)
{
// If number of elements in
// array with value 0
// is more than 1 than each
// value in new array
// will be equal to 0
if (flag > 1)
{
arr[i] = 0;
}
// If no element having value
// 0 than we will
// insert product/a[i] in new array
else if (flag == 0)
arr[i] = (prod / a[i]);
// If 1 element of array having
// value 0 than all
// the elements except that index
// value , will be
// equal to 0
else if (flag == 1 && a[i] != 0)
{
arr[i] = 0;
}
// If(flag == 1 && a[i] == 0)
else
arr[i] = prod;
}
return arr;
}
// Driver code
let n = 5;
let array = [ 10, 3, 5, 6, 2 ];
let ans = Array(n).fill(0);
ans = productExceptSelf(array, n);
for(let i = 0; i < n; i++)
{
document.write(ans[i] + " ");
}
// This code is contributed by avijitmondal1998
</script>
Producción
180 600 360 300 900
Complejidad de tiempo: O(n)
Complejidad espacial: O(1)
La array original debe atravesarse solo una vez, por lo que la complejidad del espacio es constante.
Un rompecabezas de gama de productos | Conjunto 2 (O(1) Espacio)
Problema relacionado:
construya una array a partir de XOR de todos los elementos de la array excepto el elemento en el mismo índice
Escriba comentarios si encuentra que el código/algoritmo anterior es incorrecto, o encuentre mejores formas de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA