Nowadays, especially in competitive programming, the utility of computing prefix product is quite popular and features in many problems. Hence, having a one-liner solution to it would possess a great help. Let’s discuss certain ways in which this problem can be solved.
Method 1: Using list comprehension + list slicing
This problem can be solved using the combination of the above two functions in which we use list comprehension to extend the logic to each element and then later compute the product, slicing is used to get the product to the particular index.
Python3
# Python3 code to demonstrate# Product of Prefix in list# using list comprehension + list slicing# compute proddef prod(test_list): res = 1 for ele in test_list: res = res * ele return res# initializing listtest_list = [3, 4, 1, 7, 9, 1]# printing original listprint("The original list : " + str(test_list))# using list comprehension + list slicing# Product of Prefix in listres = [prod(test_list[: i + 1]) for i in range(len(test_list))]# print resultprint("The prefix prod list is : " + str(res)) |
The original list : [3, 4, 1, 7, 9, 1] The prefix prod list is : [3, 12, 12, 84, 756, 756]
Time complexity: O(n), where n is the length of the test_list. The list comprehension + list slicing takes O(n) time
Auxiliary Space: O(n), extra space of size n is required
Method 2: Using numpy
Note: Install numpy module using command “pip install numpy”
This problem can be solved by using numpy library which has the cumprod() function that can be used to calculate the cumulative product of elements in the list.
Python3
# Python3 code to demonstrate# Product of Prefix in list# using numpyimport numpy as np# initializing listtest_list = [3, 4, 1, 7, 9, 1]# printing original listprint("The original list : " + str(test_list))# using numpyresult = np.cumprod(test_list)# print resultprint("The prefix prod list is : " + str(result))# This code is contributed by Edula Vinay Kumar Reddy |
The original list : [3, 4, 1, 7, 9, 1] The prefix prod list is : [3, 12, 12, 84, 756, 756]
Time complexity of this approach is O(n)
Auxiliary space is O(n)
Method 3: Use a loop and create an output list to store the prefix products.
steps
- Initialize an empty output list to store the prefix products.
- Initialize a variable ‘product’ to 1.
- Loop through the input list and multiply the current element with ‘product’ to get the prefix product.
- Append the prefix product to the output list.
- Update the ‘product’ variable to the current element.
- Return the output list.
Python3
def prefix_product(test_list): output = [] product = 1 for i in test_list: product *= i output.append(product) return output# input list test_list = [3, 4, 1, 7, 9, 1]print("The original list : " + str(test_list))# Getting prefix product of input list res = prefix_product(test_list)print("The prefix prod list is : " + str(res)) |
The original list : [3, 4, 1, 7, 9, 1] The prefix prod list is : [3, 12, 12, 84, 756, 756]
Time complexity: O(n) where n is the length of the input list.
Auxiliary space: O(n) to store the output list.
Method 4 : using the accumulate function from the itertools module.
step-by-step approach:
- Import the accumulate function from the itertools module
- Define the prefix_product function with the same logic as before
- The accumulate function takes two arguments: the input list and a function that specifies the operation to be applied between the elements. In this case, we use a lambda function to calculate the product of two elements.
- Convert the result into a list using the list function.
- The final output is the accumulated product of the input list.
Python3
from itertools import accumulatedef prefix_product(test_list): output = list(accumulate(test_list, lambda x, y: x * y)) return outputtest_list = [3, 4, 1, 7, 9, 1]print("The original list: " + str(test_list))res = prefix_product(test_list)print("The prefix prod list is: " + str(res)) |
The original list: [3, 4, 1, 7, 9, 1] The prefix prod list is: [3, 12, 12, 84, 756, 756]
The time complexity of this approach is O(n), where n is the length of the input list.
The auxiliary space complexity is O(n) because we need to store the prefix product list in memory.
