# 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

Output:

1152 1920 1440 2880 960 720

## Java

Output:

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

Output:

1152 1920 1440 2880 960 720

## Java

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).     (3 votes, average: 4.67 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

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

There was just a post on HN to a site that went over this exact problem. Essentially, you do two linear scans to calculate the product of every number before an index, and to calculate the product of every number after an index. Then, for each index, the answer is just multiplying those two numbers you found for that index. Guest