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
Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink.
Hide child comments as well
Confirm
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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