This question was asked in Uber interview.
Problem statement
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6]
Note: Cannot use division
Link to the question on Leetcode
Approach
The idea here is the value of an index "i" in result is the product of values from 0 to i-1 and values from i+1 to n in the given input. So, if we have some sort of data where we can get the product of 0 to i-1 and i+1 to n which will be the product of array for "i" in O(1) time complexity , then we can solve this problem in O(N) time complexity.
So, lets create two arrays of size of the given array. Lets say prefix product array and postfix product array.
Construct both the arrays such that value at index "i" in prefix product array will be the product of elements from 0 to i-1 of the original array and the value at index "i" in postfix product array will the product of elements from i+1 to n.
Now the value of an index "i" in result will be the product of prefix[i-1] and postfix[i+1].Code
Below is the link for the executable code written in python3 on replit.com
https://replit.com/@DheerajThodupun/Product-of-an-Array-except-self?lite=1