educative.io

Educative

Thoughts about 3rd solution?

Hi,

I came up with the following solution (O(n) as well):

def findProduct(arr):
  
  product = 1
  for x in arr:
    product *= x

  for i in range(len(arr)):
    arr[i] = product / arr[i]
  
  return arr

Sure, there’s an extra multiplication/division here, but do you think it is appropriate? If not, why?

1 Like

Hey Dennis,

Thanks for reaching out! This is actually a good solution for Python in my opinion. It takes O(1) space and O(n) time.

If you have any other questions/comments/suggestions, let us know!

This fails on any input with 0.

Thank you. Need to double-check everything…

My attempt to extend the “divide product by array element” approach to arrays having one or more zeros:

def findProduct(arr):
    has_one_zero = False    
    prod = 1
    for n in arr:
        if n != 0:
            prod *= n
        else:
            if has_one_zero:
                return [0] * len(arr)  # more than one zero
            has_one_zero = True
            zero_idx = arr.index(n)
            continue
    if has_one_zero:
        l_out = [0] * len(arr)
        l_out[zero_idx] = prod
        return l_out
    else:
        return [prod//arr[idx] for idx in range(len(arr))]

print(findProduct([1,2,3,6, 4]))
print(findProduct([1,2,3,0, 4]))
print(findProduct([1,0,3,0, 4]))

''' Output:
[144, 72, 48, 24, 36]
[0, 0, 0, 24, 0]
[0, 0, 0, 0, 0]
'''

I don’t think the extra overhead is too great, as any zeros are found incidentally with the creation of the product.