Product of array except self

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