Write better code: Day 2 - Product of every integer

This post originally appeared on Arjun Rajkumar's blog. Arjun runs a web development company based in Bangalore, India.

--

Day 2: Question 1

You have an array of integers, and for each index you want to find the product of every integer except the integer at that index.

Write a method get_products_of_all_ints_except_at_index() that takes an array of integers and returns an array of the products.

For example, given:

[1, 7, 3, 4]

your method would return:

[84, 12, 28, 21]

by calculating:

[7 * 3 * 4, 1 * 3 * 4, 1 * 7 * 4, 1 * 7 * 3]

Here's the catch: You can't use division in your solution!

Question from InterviewCake

If you want to follow along, feel free to post your answers below.

Comments

[Arjun Rajkumar]

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