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.

1 Like

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.

I came up with a very similar solution; glad to see it here! The only changes I would propose would be replacing range() with the more “Pythonic” enumerate(), and using floor division to ensure integer-typed results-

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

  for i, value in enumerate(arr):
    arr[i] = product // value
  
  return arr
1 Like

hey,

This is mine, considering the edge case of 0 as well:

def find_product(lst):
    new_lst = [0] * len(lst)

    product = 1
    
    for item in lst:
        if not item:
            continue
        product *= item
    
    for i, item in enumerate(lst):
        new_lst[i] = int(product / item) if item > 0 else product

    return new_lst

I came up with the same solution.
I think this is easier to understand than the solutions provided in the course.

My solution is similar too. I used reduce to make life easier. Correct me if I’m wrong, but I believe it’s O(n) time complexity and O(n) space complexity (because I created a new list without zero, might be a way to get around that…)

from functools import reduce

def find_product(lst):
    product = reduce(lambda a, b: a * b, lst)
    zero_idx = lst.index(0) if 0 in lst else -1 
    lst_wo_zero = lst[:zero_idx] + lst[zero_idx+1:]
    product_wo_zero = reduce(lambda a, b: a * b, lst_wo_zero)

    return [product / number if number != 0 else product_wo_zero for number in lst]