RUN

# Product of array except self Problem

Written By -

Input: [1,2,3,4]

Output: [24,12,8,6]

An 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

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 product array, multiply left[] and right[].

Code :

``````#include <bits/stdc++.h>
using namespace std;

void productArray(int arr[], int n)
{
if (n == 1)
{
cout << 0;
return;
}
int *left = new int[sizeof(int) *n];
int *right = new int[sizeof(int) *n];
int *prod = new int[sizeof(int) *n];

int i, j;
left[0] = 1;
right[n - 1] = 1;

for (i = 1; i < n; i++)
left[i] = arr[i - 1] *left[i - 1];

for (j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] *right[j + 1];

for (i = 0; i < n; i++)
prod[i] = left[i] *right[i];

for (i = 0; i < n; i++)
cout << prod[i] << " ";

return;
}

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);
}``````

Time Complexity: O(n)
Space 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>
using namespace std;
void productArray(int arr[], int n)
{
if (n == 1)
{
cout << 0;
return;
}

int i, temp = 1;
int *prod = new int[(sizeof(int) *n)];
memset(prod, 1, n);

for (i = 0; i < n; i++)
{
prod[i] = temp;
temp *= arr[i];
}
temp = 1;

for (i = n - 1; i >= 0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}

for (i = 0; i < n; i++)
cout << prod[i] << " ";

return;
}

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);
}``````

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

The output will be the same for both approaches:

``180,600,360,300,900``