# Educative

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.

3 Likes

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]
``````

The above will break when there are multiple zeros.

def find_product2(lst):
new_lst = [0] * len(lst)
has_zero = 0
product = 1

``````for item in lst:

if not item:
has_zero +=1
continue
product *= item
#print(item, product)

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

#new_lst[i] = int(product / item) if item > 0 else product

return new_lst``````