This post originally appeared on Arjun Rajkumar's blog. Arjun runs a web development company based in Bangalore, India.
--
Day 2: Quest...
For further actions, you may consider blocking this person and/or reporting abuse
This became simpler once I realised that the result is just the product of all the values to the left * product to the right (The question said not to use divider)
Input = [1,7,3,4,2,8]
Output = [7*3*4*2*8, 1*3*4*2*8, 1*7*4*2*8, 1*7*3*2*8, 1*7*3*4*8, 1*7*3*4*2]
Answer = 7*3*4*2*8 -> 1*3*4*2*8 -> 1*7*4*2*8 -> 1*7*3*2*8 -> 1*7*3*4*8 -> 1*7*3*4*2
multiply_left = 1 -> 1*7 -> 1*7*3 -> 1*7*3*4 ->1*7*3*4*2
multiply_right = 7*3*4*2*8 -> 3*4*2*8 -> 4*2*8 -> 2*8 -> 8
-Go thru once from left to right and store all the multipliers.
-Go thru once from right to left and multiply with all the right multipliers.
So I can do this in 2 times O[n]
Github