Mindbending Product
You are given an array ‘ARR’ of size N. You have to construct a Product Array ‘P’ of the same size such that P[i] is equal to the product of all the elements of ARR except ARR[i]. The constraint is that you are not allowed to use the division operator.

For Example:

For an array {1, 2, 3, 4, 5}: The required product array generated from the given array is {120, 60, 40, 30, 24 } This can be generated in the following manner: For generating 120 we have 2 * 3 * 4 * 5 i.e. the product of other array elements except 1. For generating 60 we have 1 * 3 * 4 * 5 i.e. the product of other array elements except 2. For generating 40 we have 1 * 2 * 4 * 5 i.e. the product of other array elements except 3. For generating 30 we have 1 * 2 * 3 * 5 i.e. the product of other array elements except 4. For generating 24 we have 1 * 2 * 3 * 4 i.e. the product of other array elements except 5.

Input format:

The first line contains an Integer 'T' which denotes the number of test cases/queries to be run. Then the test cases follow. The first line of input for each test case/query contains an integer N representing the size of the array. The second line of input for each test case/query contains N space-separated integers representing the elements of the array.

Output Format:

For each test case, print 'N' single space-separated integers denoting elements of the product array P. Output for every test case will be printed in a separate line.

Note:

1. You do not need to print anything, it has already been taken care of. Just implement the function. 2. The value of P[i] will fit into a 64-bit data type.

Constraints:

1

Question

Mindbending Product

You are given an array ‘ARR’ of size N. You have to construct a Product Array ‘P’ of the same size such that P[i] is equal to the product of all the elements of ARR except ARR[i]. The constraint is that you are not allowed to use the division operator.

For Example:

For an array {1, 2, 3, 4, 5}:
The required product array generated from the given array is {120, 60, 40, 30, 24 }

This can be generated in the following manner:

For generating 120 we have 2 * 3 * 4 * 5 i.e. the product of other array elements except 1.
For generating 60 we have 1 * 3 * 4 * 5  i.e. the product of other array elements except 2.
For generating 40 we have 1 * 2 * 4 * 5  i.e. the product of other array elements except 3.
For generating 30 we have 1 * 2 * 3 * 5  i.e. the product of other array elements except 4.
For generating 24 we have 1 * 2 * 3 * 4  i.e. the product of other array elements except 5.

Input format:

The first line contains an Integer 'T' which denotes the number of test cases/queries to be run. 
Then the test cases follow. 

The first line of input for each test case/query contains an integer N representing the size of the array.

The second line of input for each test case/query contains N space-separated integers representing the elements of the array.

Output Format:

For each test case, print 'N' single space-separated integers denoting elements of the product array P.

Output for every test case will be printed in a separate line.

Note:

1. You do not need to print anything, it has already been taken care of. Just implement the function.
2. The value of P[i] will fit into a 64-bit data type.

Constraints:

1 <= T <= 50
1 <= N <= 10
1 <= ARR [i] <= 20

Time Limit: 1 sec

Accepted Answer

Brute Force

Create an array ‘P’ of size N.
If n = 1 then initialize P[0]=0 and return.
Run a loop from i = 0 to i = N-1, and initialize a variable currentProduct = 1 and run another nested loop from j = 0 to j = N-1.
- If i == j skip this element
- Otherwise CURRENT_PRODUCT *= ARR[j]
Now assign the CURRENT_PRODUCT at P[i]
- P[i] = CURRENT_PRODUCT
Now P array has the required answer, therefore, return the P array.

Space Complexity: O(1)Explanation:

O(1), We are using constant extra space.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the number of elements in the array.

Since we are iterating over the elements of the array in two nested for loops of size N. Therefore the time complexity here grows by the order O(N^2).

Accepted Answer

Optimal Approach with 2 extra array

Create an array ‘P’ of size N.
If N = 1 then initialize P[0]=0 and return.
Create two array prefix and suffix.
- Prefix array stores product till i’th position excluding i’th element from the left side.
- Suffix array stores product till i’th position excluding i’th element from the right side.
Initialize Prefix[0] = 1 and start loop from i = 1 to i = N - 1
- PREFIX[i] = PREFIX[i-1] * ARR[i-1]
- The PREFIX[i] will store the product of all the elements till i-1 index from the left side.
Initialize SUFFIX[N-1] = 1 and start loop from i = N-2 to i = 0
- SUFFIX[i] = SUFFIX[i+1] * ARR[i+1]
- The SUFFIX[i] will store the product of all the elements till i+1 index from the right side.
Now run a loop from i = 0 to i = N - 1
- P[i] = PREFIX[i] * SUFFIX[i]
- Now P[i] has the product of all the elements except the i’th element.
Now P has the required answer, therefore, return the P array.

Space Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

Since we are using three arrays of size N.

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

Creating PREFIX, SUFFIX and P arrays requires only one traversal for each array.

Accepted Answer

Optimal Approach

Create an array ‘P’ of size N.
If N = 1 then initialize P[0]=0 and return.
Initialize the P array with 1.
Initialize a variable TEMP = 1 which will be used in place of the prefix array and run a loop from i = 0 to i = N - 1 and Initialize
- P[i] = TEMP
- TEMP *= ARR[i]
Again re-initialize TEMP = 1 now this will be used in place of suffix array and at the same time, we will multiply it with P[i] which has the prefix value to get the required answer.
Run a loop from i = N - 1 to i = 0 and
- P[i] *= TEMP
- TEMP[i] *= ARR[i]
Now P array has the required answer, therefore, return the P array.

Space Complexity: O(1)Explanation:

O(1), We are using constant extra space.

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

All the operations require only one iteration of traversal.

You are given an array ‘ARR’ of size N. You have to construct a Product Array ‘P’ of the same size such that P[i] is equal to the product of all the elements of ARR except ARR[i]. The constraint is that you are not allowed to use the division operator.

For Example:

Input format:

Output Format:

Note:

Constraints:

Top Wipro Project Engineer interview questions & answers

Popular interview questions of Project Engineer

Top HR questions asked in Wipro Project Engineer