Skip to content

Instantly share code, notes, and snippets.

@toritsejuFO
Last active May 2, 2021 17:39
Show Gist options
  • Save toritsejuFO/6641fbb8099c889c97bb628215c9b540 to your computer and use it in GitHub Desktop.
Save toritsejuFO/6641fbb8099c889c97bb628215c9b540 to your computer and use it in GitHub Desktop.
from functools import reduce
def get_products(nums):
products = []
if nums == None or len(nums) == 0 or len(nums) == 1:
return products
for i, el in enumerate(nums):
nums_to_multiply = nums[:i] + nums[i+1:]
product = reduce(lambda x, y: x * y, nums_to_multiply)
products.append(product)
return products
if __name__ == '__main__':
nums = [4, 5, 10, 2]
products = get_products(nums)
print(products)
@toritsejuFO
Copy link
Author

Thanks a lot for your feedback @meekg33k.

Yeah, it's equivalent to a nested loop, because reduce takes about O(n) since it iterates through all the elements, even though it's n-1 elements in this case, that's still ~n. And then I'm also iterating through each element as well. So time complexity is O(n^2), because for each element I go through in my iteration, reduce goes through all other elements.

I initially thought I could do it without having to create a new array, but I would be modifying the existing one, making it impossible to get the subsequent products as I proceed. So I had to create a new array to hold each product to avoid mutation of the original. This implies double the memory space, so not very memory efficient if we consider that nums is a very large array. I'm already excited to see your incoming solution and how you handle this.

Also, I store the other elements to be multiplied in a temporary array as well during my iteration (I could have passed directly to reduce, but it wouldn't be easily readable), but each iteration does away the space every time, so that was acceptable to me.

Thanks again, I really appreciate.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment