One of the problem that is basically a subproblem for many complex problems, finding product number till a certain number in list in python, is commonly encountered and this particular article discusses possible solutions to this particular problem.
Method #1 : Naive method The most common way this problem can be solved is using a loop and just multiplying the occurrences of elements that are till given number K.
Python3
# Python 3 code to demonstrate # Elements Product till K value# using naive method # initializing list test_list = [1, 7, 5, 6, 3, 8] # initializing k k = 6# printing list print ("The list : " + str(test_list)) # using naive method # Elements Product till K valueres = 1for i in test_list : if i <= k : res *= i # printing the productprint ("The product till K : " + str(res)) |
The list : [1, 7, 5, 6, 3, 8] The product till K : 90
Time Complexity: O(n) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(1), constant extra space is needed
Method #2 : Using list comprehension This method achieves this task in a similar way, but in a more concise manner. List comprehension always lowers the lines of codes in the program even though runs a similar approach in the background.
Python3
# Python 3 code to demonstrate # Elements Product till K value# using list comprehension# getting Product def prod(val) : res = 1 for ele in val: res *= ele return res # initializing list test_list = [1, 7, 5, 6, 3, 8] # initializing k k = 6# printing list print ("The list : " + str(test_list)) # using list comprehension # Elements Product till K valueres = prod([i for i in test_list if i <= k]) # printing the intersection print ("The product till K : " + str(res)) |
The list : [1, 7, 5, 6, 3, 8] The product till K : 90
Method #3: Using NumPy
Note: Install numpy module using command “pip install numpy”
This method uses the functionality of NumPy library, which makes this code optimized and faster.
Python3
# importing numpy libraryimport numpy as np# initializing listtest_list = [1, 7, 5, 6, 3, 8]# initializing kk = 6# printing listprint("The list : ", test_list)# using numpy# Elements Product till K valueres = np.prod([i for i in test_list if i <= k])# printing the productprint("The product till K : ", res) |
Output:
The list : [1, 7, 5, 6, 3, 8]
The product till K : 90
Time Complexity: O(N)
Space Complexity: O(N)
Method #4: Using reduce() function from functools module.
The algorithm for this program is as follows:
- Initialize a list of integers called test_list and a threshold value called k.
- Use list comprehension to extract all elements from test_list that are less than or equal to k.
- Use the reduce() function from functools module to multiply all elements from the filtered list.
- Store the product in a variable called prod.
- Print both the original list and the product till K.
Python3
from functools import reducetest_list = [1, 7, 5, 6, 3, 8]k = 6prod = reduce((lambda x, y: x * y), [i for i in test_list if i <= k])print("The list : ", test_list)print("The product till K : ", prod) |
The list : [1, 7, 5, 6, 3, 8] The product till K : 90
The time complexity of the program is O(n), where n is the length of the original list. This is because the program only loops through the list once to filter out elements that are greater than k, and then performs a reduce() operation on the filtered list.
The auxiliary space of the program is also O(n) because a new list is created to store the filtered elements. However, since the filtered list is smaller than the original list, the space complexity could be lower than O(n) in certain cases.
Method 5 : Using the built-in function math.prod().
steps
Import the math module to use the prod() function.
Initialize the list and k value as in the provided code.
Filter out the elements greater than k using a list comprehension.
Calculate the product of the filtered list using math.prod().
Print the product.
Python3
import math# initializing list test_list = [1, 7, 5, 6, 3, 8] # initializing k k = 6# printing list print("The list : " + str(test_list)) # using math.prod() function # Elements Product till K valuefiltered_list = [i for i in test_list if i <= k]res = math.prod(filtered_list)# printing the intersection print("The product till K : " + str(res)) |
OUTPUT ; The list : [1, 7, 5, 6, 3, 8] The product till K : 90
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(k), where k is the number of elements in the list that are less than or equal to k.
