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.
leave a comment
0 Comments