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?
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.
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
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