RUN


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

Report Error/ Suggestion

Related Posts:

[yuzo_views]



Interview Questions



CopyRight © 2020

CopyRight © 2020