Python – Suffix Product in list
Nowadays, especially in the field of competitive programming, the utility of computing suffix 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 way in which this problem can be solved.
Method: Using list comprehension + loop + list slicing This problem can be solved using the combination of above two functions in which we use list comprehension to extend logic to each element, explicit product function to get the product along, slicing is used to get product till the particular index.
Python3
# Python3 code to demonstrate # Suffix List Product # using list comprehension + loop + list slicing # compute prod def prod(test_list): res = 1 for ele in test_list: res = res * ele return res # initializing list test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] # printing original list print ( "The original list : " + str (test_list)) # using list comprehension + loop + list slicing # Suffix List Product test_list.reverse() res = [prod(test_list[ : i + 1 ]) for i in range ( len (test_list))] # print result print ( "The suffix product list is : " + str (res)) |
The original list : [3, 4, 1, 7, 9, 1] The suffix product list is : [1, 9, 63, 63, 252, 756]
Time Complexity: O(n), where n is the length of the input list. This is because we’re using the list comprehension + loop + list slicing which has a time complexity of O(n) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list.
Approach : Using Cumulative Product in single iteration
This approach calculates cumulative product for the input list in a single iteration.
Python3
#Python3 code to demonstrate #Suffix List Product #using cumulative product #initializing list test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] #printing original list print ( "The original list : " + str (test_list)) #using cumulative product #Suffix List Product result = [] prod = 1 for i in range ( len (test_list) - 1 , - 1 , - 1 ): prod = prod * test_list[i] result.append(prod) #print result print ( "The suffix product list is : " + str (result)) #This code is contributed by Edula Vinay Kumar Reddy |
The original list : [3, 4, 1, 7, 9, 1] The suffix product list is : [1, 9, 63, 63, 252, 756]
Time complexity: O(n)
Auxiliary Space: O(n)
Explanation
In this approach, we calculate the cumulative product in a single iteration from the end of the list to the start. The calculation starts with a default product of 1. For every iteration, the product is updated as the current product multiplied by the current list element and the result is appended to a list. Finally, the list is reversed to get the desired suffix product.
Approach : using NumPy
Python3
import numpy as np def suffix_list_product(lst): return np.cumprod(lst[:: - 1 ])[:: - 1 ].tolist() # test the function with the sample list test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] #printing original list print ( "The original list : " + str (test_list)) print ( "The suffix product list is : " + str ( list ( reversed (suffix_list_product(test_list))))) #This code is contributed by Vinay Pinjala. |
Output:
The original list : [3, 4, 1, 7, 9, 1] The suffix product list is : [1, 9, 63, 63, 252, 756]
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach: Using reduce() function.
Python3
#Python3 code to demonstrate #Suffix List Product #using reduce function from functools import reduce def suffix_product(nums): result = [ 1 ] * len (nums) for i in range ( len (nums) - 1 , - 1 , - 1 ): result[i] = reduce ( lambda x, y: x * y, nums[i:]) return result #initializing list test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] #printing original list print ( "The original list : " + str (test_list)) #using cumulative product #Suffix List Product result = [] prod = 1 result = suffix_product(test_list) result.reverse() #print result print ( "The suffix product list is : " + str (result)) #This code is contributed by tvsk |
The original list : [3, 4, 1, 7, 9, 1] The suffix product list is : [1, 9, 63, 63, 252, 756]
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach : Using the accumulate() function from itertools:
Algorithm:
1.Initialize the test list with some values.
2.Use the accumulate function from the itertools module to calculate the cumulative product of the reversed list.
3.The lambda function passed as an argument to the accumulate function is used to multiply the current and previous values.
4.Convert the output of accumulate to a list and reverse it to get the suffix product list.
5.Print the suffix product list.
Python3
# Importing the accumulate function from itertools module from itertools import accumulate # Initializing the test list test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] #printing original list print ( "The original list : " + str (test_list)) # Calculating the suffix product list using accumulate and reverse functions # The accumulate function is used to get the cumulative product of the reversed list # The lambda function inside accumulate is used to multiply the current and previous values suffix_list = list (accumulate( reversed (test_list), lambda x, y: x * y)) # Printing the suffix product list print ( "The suffix product list is : " + str (suffix_list)) #This code is contributed by Jyothi pinjala |
The original list : [3, 4, 1, 7, 9, 1] The suffix product list is : [1, 9, 63, 63, 252, 756]
Time Complexity:
The time complexity of the algorithm is O(n), where n is the length of the input list. This is because the accumulate function and the list function both take O(n) time, and the lambda function takes constant time.
Auxiliary Space:
The space complexity of the algorithm is also O(n), as we are creating a new list to store the suffix product values. The accumulate function also creates a temporary list to store the cumulative product values.
Contact Us