Recent Posts

Product of array except self

Written by

Anshuman Raina

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

  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 &lt; n; i++)
	left[i] = arr[i - 1] *left[i - 1];

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

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

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

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 &lt; n; i++)
{
	prod[i] = temp;
	temp *= arr[i];
}
temp = 1;

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

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

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
Product of array except self