Last Updated: 10 Sep, 2020
Mindbending Product
Easy
Asked in companies
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
Approaches
- 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.
- 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.
- 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.
Similar problems