DEV Community

loading...

Write better code: Day 2 - Product of every integer

arjunrajkumar profile image Arjun Rajkumar Updated on ・1 min read

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.

Discussion (1)

pic
Editor guide
Collapse
arjunrajkumar profile image
Arjun Rajkumar Author • Edited

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]

Code
Github