There is an array of integers, lets say 3,5,7,9. You are supposed to create another array and populate it such that the second array's 0th position should be a product of all numbers from the first array excluding the number at its 0th position, meaning it should be 5x7x9(excluding 3), number at the index 1 of the second array will be product of 3x7x9 (excluding 5).
The first answer that came up to my mind was having 2 for loops which will lead to a time complexity of O(n2). Later I figured this:
Multiplying all the numbers in the first array(3x5x7x9), and while populating the second array I will divide this product by the number at that position. divide by 3 if I am populating the 0th position, divide by 5 if I am populating the 1st position and so on. This would bring down the complexity from O(n2) to probably O(2n).
But the interviewer says division is not allowed. I could not think of anything else but storing the different possible multiples in some kind of a data structure and using it while populating. I gave up, but when asked for the answer he said he would maintain 2 arrays of forward and backward multiples. When asked about the space complexity issue of the solution, he said it could be optimized.