# 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 ` `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 ` `#include ` ` `  `/* 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

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

 `= 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=0; i--) ` `  ``{ ` `    ``prod[i] *= temp; ` `    ``temp *= arr[i]; ` `  ``} ` ` `  `  ``/* print the constructed prod array */` `  ``for` `(i=0; i

## 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= ``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

 `= 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)

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