You have a list of integers, and for each index, you want to find the product of every integer except the integer at that index — InterviewCake

This problem is straight outta InterviewCake. Attempted to solve it but got stuck and eventually looked into the solution. Sadly, the solution wasn’t visual enough for me, although it was pretty descriptive. As a visual learner, I couldn’t stop but write this post with some visuals that are just some neat versions of the ones I jotted down on my notebook!

Here goes some more description on the problem:

Write a function get_products_of_all_ints_except_at_index() that takes a list of integers and returns a list of the products.

For example, given:

[1, 7, 3, 4]

Your function 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!

Notice that, doing it with division would be an easy cake! We could basically multiply all the numbers in O(n). and then divide by that product by the item at the current index. Sadly, we can’t do that.

We need to think cleverly!

The Pattern

Let’s take a closer look at our I/O: