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!
If you want to follow along, feel free to post your answers below.
Top comments (1)
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