2
\$\begingroup\$

Coding problem:

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

My solution:

arr = np.array([1, 2, 3, 4, 5])

def coding_solution(_arr):
    ind = 0
    new_arr = []
    for n in range(len(_arr)):
        v = 1
        for m, i in enumerate(_arr):
            v *= i if m != ind else 1
        new_arr.append(v)
        ind += 1
    return np.array(new_arr)

Output: [120, 60, 40, 30, 24]

Is there a faster or less space consuming solution? It takes longer to run then I would've expected or would think is acceptable.

\$\endgroup\$
3
\$\begingroup\$

Review:

So there are some changes that can be made. As you are running a nested for loop that should be the first candidate for removal, python isn't the best with lots of loops. I've made some changes below to improve your code.

  • Here we actually use n, instead of ind, they are the same, so ind is excessive
  • I've expanded the if ... else block as this improves readability
  • I've changed i for x as this is easier to quickly differentiate from 1

def coding_solution(_arr):
    new_arr = []
    for n in range(len(_arr)):
        v = 1
        for m, x in enumerate(_arr):
            if m != n:
                v *= x 
            else:
                v *= 1
        new_arr.append(v)
    return np.array(new_arr)

Alternate solutions:

I have two methods that work, one is pure python (using two core libraries), but could include numpy; the other is all numpy. They both work on a similar principal, that is that all new values are the same product (the entire array) divided by the value at the same index in the original array. Therefore, you can just divide the product of the entire array by each value in the original array, as long as there are no zero values (thanks One Lyner!).

Pure python:

from functools import reduce
from operator import mul

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

def f(_arr):
    arr_prod = reduce(mul, _arr)  # You could use np.prod(_arr) instead of reduce(...)
    return [arr_prod / x for x in _arr]

The pure python function could be a single line, but then you might end up computing the product of the entire array on every iteration.

Numpy


import numpy as np

arr = np.array([1, 2, 3, 4, 5])

def g(_arr):
    return np.ones(_arr.shape) * _arr.prod() / _arr

# Even more succinct, thanks Graipher
def h(_arr):
    return _arr.prod() / _arr

This Numpy solution would be vectorised and would scale well, but may be slower on smaller arrays. It works by creating a new np.array of all 1; multiplying it by the product, so all the values are the product; finally dividing the 'product array' by the original array, which is element-wise.

\$\endgroup\$
  • 1
    \$\begingroup\$ Just _arr.prod() / _arr also works (since int does not know how to divide by a numpy.array, it is delegated to the array which does know how to divide and scale itself). \$\endgroup\$ – Graipher Feb 11 at 11:55
  • 2
    \$\begingroup\$ corner case: note this only works if there is no zero in the array! \$\endgroup\$ – One Lyner Feb 11 at 15:56
1
\$\begingroup\$

To take into account the case where there is some zero values in the array, it's best to avoid divisions. To make this efficiently, you can do two passes, one computing the product of elements before and one computing the product of elements after.

Pure python:

def products_of_others(a):
     L = len(a)
     r = [1]*L
     after = before = 1
     for i in range(1,L):
         before *= a[i-1]
         r[i] = before
     for i in range(L-2,-1,-1):
         after *= a[i+1]
         r[i] *= after
     return r

Numpy:

def products_of_others(a):
     after = numpy.concatenate([a[1:], [1]])
     before = numpy.concatenate([[1], a[:-1]])
     a = numpy.cumprod(after[::-1])[::-1]
     b = numpy.cumprod(before)
     return a * b
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.