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. (Can't use division)

Question

I am currently working on practice interview questions. Attached is a screenshot of the question I'm working on below

I tried with the brute force approach of using nested loops with the intent of refactoring out the nested loop, but it still failed the tests in the brute force approach.

Here is the code that I tried:

def get_products_of_all_ints_except_at_index(int_list):

# Make a list with the products
products = []

for i in int_list:
    for j in int_list:
        if(i != j):
            k = int_list[i] * int_list[j]
            products.append(k)


return products

I am curious to both the brute force solution, and the more efficient solution without using nested loops.

Answer 1

Linear algorithm using cumulative products from the right side and from the left side

def productexcept(l):
    n = len(l)
    right = [1]*n
    for i in reversed(range(n-1)):
        right[i] = right[i + 1] * l[i+1]
    #print(right)
    prod = 1
    for i in range(n):
        t = l[i]
        l[i] = prod * right[i]
        prod *= t
    return l

print(productexcept([2,3,7,5]))

>> [105, 70, 30, 42]

Answer 2

Assume N to be a power of 2.

Brute force takes N(N-2) products. You can improve on that by precomputing the N/2 products of pairs of elements, then N/4 pairs of pairs, then pairs of pairs of pairs, until you have a single pair left. This takes N-2 products in total.

Next, you form all the requested products by multiplying the required partial products, in a dichotomic way. This takes Lg(N)-1 multiplies per product, hence a total of N(Lg(N)-1) multiplies.

This is an O(N Log N) solution.

---

Illustration for N=8:

Using 6 multiplies,

a  b  c  d  e  f  g  h
 ab    cd    ef    gh
   abcd        efgh

Then with 16 multiplies,

b.cd.efgh
a.cd.efgh
ab.d.efgh
ab.c.efgh
abcd.f.gh
abcd.e.gh
abcd.ef.h
abcd.ef.g

The desired expressions can be obtained from the binary structure of the numbers from 0 to N-1.

Answer 3

Here's a solution using a recursive function instead of a loop:

from functools import reduce


def get_products_of_all_ints_except_at_index(int_list, n=0, results=[]):
    new_list = int_list.copy()
    if n == len(int_list):
        return results
    new_list.pop(n)
    results.append(reduce((lambda x, y: x * y), new_list))
    return get_products_of_all_ints_except_at_index(int_list, n+1, results)


int_list = [1, 7, 3, 4]
print(get_products_of_all_ints_except_at_index(int_list))
# expected results [84, 12, 28, 21]

Output:

[84, 12, 28, 21]

Answer 4

I've come up with this:

def product(larg):
    result = 1
    for n in larg:
        result *= n
    return result

List = [1, 7, 3, 4]
N = len(List)
BaseList = [List[0:i] + List[i+1:N] for i in range(N)]
Products = [product(a) for a in BaseList]

print(Products)

From the input list List, you create a list of lists where the proper integer is removed in each one. Then you just build a new list with the products of those sublists.

Answer 5

If you want to get the index of each elements in a list, you should try for i in range(len(int_list)). for i in int_list is in fact returning the values in the list but not the index. So the brute force solution should be:

def get_products_of_all_ints_except_at_index(int_list):
# Make a list with the products
products = []

for i in range(len(int_list)):
    k = 1
    for j in range(len(int_list)):
        if(i != j):
            k *= int_list[j]
    products.append(k)

return products

Answer 6

Brute force

Your brute force approach does not work for multiple reasons:

(I'm assuming at least fixed indentation)

1. List index out of range

    for i in int_list
   

   This already gives you i which is an element of the list, not an index. When i is 7,

   int_list[i]
   

   is not possible any more.

   The loops should be for ... in range(len(int_list)).

2. With that fixed, the result contains too many elements. There are 12 elements in the result, but only 4 are expected. That's because of another indentation issue at products.append(...). It needs to be outdented 2 steps.

3. With that fixed, most k are overwritten by a new value each time i*j is calculated. To fix that, start k at the identity element for multiplication, which is 1, and then multiply int_list[j] onto it.

The full code is now

def get_products_of_all_ints_except_at_index(int_list):
products = []

for i in range(len(int_list)):
    k = 1
    for j in range(len(int_list)):
        if i != j:
            k *= int_list[j]
    products.append(k)

return products

Optimization

I would propose the "brute force" solution as an answer first. Don't worry about performance as long as there are no performance requirements. That would be premature optimization.

The solution with division would be:

def get_products_of_all_ints_except_at_index(int_list):
    products = []

    product = 1
    for i in int_list:
        product *= i

    for i in int_list:
        products.append(product//i)

    return products

and thus does not need a nested loop and has linear Big-O time complexity.

A little exponent trick may save you the division: simply multiply by the inverse:

for i in int_list:
    products.append(int(product * i ** -1))

Answer 7

If you are allowed to use imports and really ugly list comprehensions you could try this:

from functools import reduce

l = [1,7,3,4]
[reduce(lambda x,y: x*y, [l[i] for i in range(len(l)) if i != k],1) for k,el in enumerate(l)]

If you are not allowed to use functools you can write your own function:

def prod(x):
  prod = 1
  for i in x:
    prod = prod * i
  return prod

l = [1,7,3,4]
[prod([l[i] for i in range(len(l)) if i != k]) for k,el in enumerate(l)]

I leave it as an exercise to the reader to put the two solutions in a function.