CODEWITHSUNDEEP
pythonprecisionfloating-accuracy
William M.
William M.

Reputation: 233

Given a list of integers, find the list consisting of the product of all elements but the current index

I am working with Python 3.8.

Consider a list of (strictly) positive integers, for example

L = [1,2,3,4,5]

My task is to calculate a new list such that its ith element is the product of all elements in L but the ith one. So, for L given, our result will be

R = [120, 60, 40, 30, 24]

Obviously, I can do

R = [functool.reduce(operator.mul, [L[ix] for ix in range(len(L)) if ix != k]) for k in range(len(L))]

This, however, has quadratic time complexity.

Mathematically, it would be much more efficient to simply multiply all elements of L and then construct R with a comprehension by dividing this product by each element of L. This, of course, has a floating-point accuracy limitation and it does not work in my computer for large lists (len(L) around 10^4 with numbers between 1 and 1000).

Any ideas on doing this? Notice that should the second approach work, the time complexity is reduce to linear.

Upvotes: 1

Views: 451

Answers (1)

jmd_dk
jmd_dk

Reputation: 13120

You're in luck because Python has arbitrary precision integers! So you can in fact just multiply them all together and then divide by the given integer:

L = [1,2,3,4,5]

prod = 1
for el in L:
    prod *= el

R = [prod//el for el in L]

Note that integer division // is used. As all elements el are factors of prod by construction, this always results in exact division. Using just / would result in floating-point division, possibly introducing errors.

Upvotes: 3

Related Questions