{"post":"

Product of array except self problem

Input: [1,2,3,4]

Output: [24,12,8,6]

Array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Note: Please solve it without division and in O(n).

# Brute Force

Construct a temporary array left[] such that left[i] contains product of all elements on left of arr[i] excluding arr[i].
Construct another temporary array right[] such that right[i] contains product of all elements on on right of arr[i] excluding arr[i].
To get product array, multiply left[] and right[].

Code :

#include <bits/stdc++.h>\nusing namespace std;\nvoid productArray(int arr[], int n)\n{\nif (n == 1)\n{\ncout << 0;\nreturn;\n}\nint *left = new int[sizeof(int) *n];\nint *right = new int[sizeof(int) *n];\nint *prod = new int[sizeof(int) *n];
\nint i, j;\nleft[0] = 1;\nright[n - 1] = 1;\n\nfor (i = 1; i &lt; n; i++)\n\tleft[i] = arr[i - 1] *left[i - 1];\n\nfor (j = n - 2; j &gt;= 0; j--)\n\tright[j] = arr[j + 1] *right[j + 1];\n\nfor (i = 0; i &lt; n; i++)\n\tprod[i] = left[i] *right[i];\n\nfor (i = 0; i &lt; n; i++)\n\tcout &lt;&lt; prod[i] &lt;&lt; \" \";\n\nreturn;\n
\n}
\nint main()\n{\nint arr[] = { 10, 3, 5, 6, 2 };\nint n = sizeof(arr) / sizeof(arr[0]);\ncout << \"The product array is: \\n\";\nproductArray(arr, n);\n}

Time Complexity: O(n)
\nSpace Complexity: O(n)

# Optimized Solution

The approach here will be to minimize the space required by the left and the right array.

Code :

#include <bits/stdc++.h>\nusing namespace std;\nvoid productArray(int arr[], int n)\n{\n\tif (n == 1)\n\t{\n\t\tcout << 0;\n\t\treturn;\n\t}\nint i, temp = 1;\nint *prod = new int[(sizeof(int) *n)];\nmemset(prod, 1, n);\n\nfor (i = 0; i &lt; n; i++)\n{\n\tprod[i] = temp;\n\ttemp *= arr[i];\n}\ntemp = 1;\n\nfor (i = n - 1; i &gt;= 0; i--)\n{\n\tprod[i] *= temp;\n\ttemp *= arr[i];\n}\n\nfor (i = 0; i &lt; n; i++)\n\tcout &lt;&lt; prod[i] &lt;&lt; \" \";\n\nreturn;\n
\n}
\nint main()\n{\nint arr[] = { 10, 3, 5, 6, 2 };\nint n = sizeof(arr) / sizeof(arr[0]);\ncout << \"The product array is: \\n\";\nproductArray(arr, n);\n}

Time Complexity: O(n)
\nSpace Complexity: O(n)

The output will be the same for both approaches:

180,600,360,300,900

\n","title":"Product of array except self","authorDetails":{"name":"Anshuman Raina","slug":"anshuman-raina"},"seo":{"title":"Product of array except self"},"description":"Product of array except self problem solution and explanation in C++ with and without using extra space in O(n) time complexity.","slug":"product-of-array-except-self/","articleId":"636a83447bb1ce5072622b91","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}