Tutorialspoint.dev

A Product Array Puzzle

Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator and in O(n).

Example :
arr[] = {10, 3, 5, 6, 2}
prod[] = {180, 600, 360, 300, 900}


Algorithm:
1) Construct a temporary array left[] such that left[i] contains product of all elements on left of arr[i] excluding arr[i].
2) Construct another temporary array right[] such that right[i] contains product of all elements on on right of arr[i] excluding arr[i].
3) To get prod[], multiply left[] and right[].

Implementation:

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) 
{ 
    /* 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; 
      
    /* Rightmost 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: "; 
    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)
{
  /* 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;
  
  /* Rightmost 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) 
    {
        // 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;
  
        /* Rightmost 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 aboe 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

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) 
    {
          
        // 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;
  
        /* Rightmost 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 aboe function */
    public static void Main() 
    {
        int []arr = {10, 3, 5, 6, 2};
        int n = arr.Length;
        Console.Write("The product array is : ");
          
        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) 
{
    // 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;
  
    // Rightmost 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 : ";
productArray($arr, $n);
  
// This code has been contributed by anuj_67.
?>


Output :



The product array is : 
180 600 360 300 900

Time Complexity: O(n)
Space Complexity: O(n)
Auxiliary Space: O(n)

The above method can be optimized to work in space complexity O(1). Thanks to Dileep for suggesting the below solution.

C/C++

void productArray(int arr[], int n)
{
  int i, temp = 1;
  
  /* Allocate memory for the product array */
  int *prod = (int *)malloc(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++)
    printf("%d ", prod[i]);
  
  return;
}

Java

class ProductArray 
{
    void productArray(int arr[], int n) 
    {
        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):
  
    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) 
    {
        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) 
    {
        $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 : ";
        productArray($arr, $n);
      
// This code is contributed by anuj_67.
?>


Output :

The product array is : 
180 600 360 300 900

Time Complexity: O(n)
Space Complexity: O(n)
Auxiliary Space: O(1)


A product array puzzle | Set 2 (O(1) Space)

Related Problem :
Construct an Array from XOR of all elements of array except element at same index

Please write comments if you find the above code/algorithm incorrect, or find better ways to solve the same problem.



This article is attributed to GeeksforGeeks.org

tags:

Arrays Mathematical Accolite Amazon D-E-Shaw Opera Accolite Amazon D-E-Shaw Opera Arrays Mathematical
Prev Next
More topics on Arrays

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Arrays Count all distinct pairs with ...
Arrays Minimum number of swaps requir...
Arrays
Arrays Find Union and Intersection of...
Arrays Maximum triplet sum in array
Arrays Find a triplet that sum to a g...