Replace each element of the array with product of every other element without using division operator

Given an array of integers, replace each element of the array with product of every other element in the array without using division operator.

 

For example,


Input:  { 1, 2, 3, 4, 5 }
Output: { 120, 60, 40, 30, 24 }
 

Input:  { 5, 3, 4, 2, 6, 8 }
Output: { 1152, 1920, 1440, 2880, 960, 720 }

 


 

Naive approach would be to calculate product of all elements in the left sub-array and right sub-array for each element of the array. The time complexity of above solution is O(n2).

 

We can solve this problem in linear time by using two auxiliary arrays left[] and right[] where left[i] stores the product of all elements in the sub-array A[0..i-1] and right[i] stores the product of all elements in sub-array A[i+1..n-1]. Now for each element A[i], we simply replace it with product of its left-subarray and right-subarray (i.e. A[i] = left[i] * right[i]).

 
C++ implementation –
 

Download   Run Code

Output:

1152 1920 1440 2880 960 720

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 

We can use recursion to solve this problem in linear time and constant space. The idea is to recursively calculate the product of all elements in the right sub-array and pass left-subarray product in function arguments.

 
C++ implementation –
 

Download   Run Code

Output:

1152 1920 1440 2880 960 720

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1) (if we ignore recursion stack space, no auxiliary space is used).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
foobar
Guest
foobar

Another O(n) approach without recursion.

-> Find product of right of each number from left and store it in array1.
-> Find product of left of each number from right and store it in array2.
-> Now, multiple array1 and array2 at each index to get the final array (array2 can be avoided by taking care of the multiplication inline)

wpDiscuz