The prefix array is quite famous in the programming world. This article would discuss a variation of this scheme. This deals with the cumulative list product till a False value, and again starts cumulation of product from occurrence of True value. Let’s discuss certain way in which this can be performed.
Method #1 : Using Naive Method In the naive method, we just construct the new list comprising of the product of prev. value of list until False and restarts the procedure once a True value is encountered.
Python3
# Python3 code to demonstrate # Multiplication till Null value# using naive method # initializing list of liststest_list = [1, 3, 4, False, 4, 5, False, 7, 8]# printing original listprint ("The original list is : " + str(test_list))# Multiplication till Null value# using naive methodfor i in range(1, len(test_list)): if test_list[i]: test_list[i] *= test_list[i - 1] else: test_list[i] = 1# printing resultprint ("The computed modified new list : " + str(test_list)) |
The original list is : [1, 3, 4, False, 4, 5, False, 7, 8] The computed modified new list : [1, 3, 12, 1, 4, 20, 1, 7, 56]
Time complexity: O(n), where n is the length of the test_list.
Auxiliary Space: O(n), extra space of size n is required
Method#2: Using Recursive method.
The function multiply_till_null() takes in the input list test_list and the starting index index as parameters. If the index is equal to the length of the list, it returns the modified list. If the element at the current index is null, it sets the value to 1. Otherwise, it multiplies the current element with the previous element in the list. The function then recursively calls itself with the updated list and index incremented by 1. Finally, the function is called with the input list and starting index of 1 to begin the recursion.
Python3
def multiply_till_null(test_list, index): if index == len(test_list): return test_list if not test_list[index]: test_list[index] = 1 else: test_list[index] *= test_list[index - 1] return multiply_till_null(test_list, index + 1)# initializing list of liststest_list = [1, 3, 4, False, 4, 5, False, 7, 8]# printing original listprint("The original list is:", test_list)# calling recursive functionresult = multiply_till_null(test_list, 1)# printing modified listprint("The computed modified new list:", result) |
The original list is: [1, 3, 4, False, 4, 5, False, 7, 8] The computed modified new list: [1, 3, 12, 1, 4, 20, 1, 7, 56]
The time complexity of this method is O(n) because the function is called recursively n times, where n is the length of the input list.
The auxiliary space is also O(n) because the function call stack grows with each recursive cal
Method #3: Using Iterative Method
The iterative method involves iterating over the input list and multiplying the elements until a null value is encountered. We can use a for loop to iterate over the list and keep track of the previous element in a variable. Whenever a null value is encountered, we set the current element to 1, and continue with the iteration.
step-by-step approach
Initialize a variable prev to 1.
Iterate over the elements of the input list using a for loop.
For each element in the list, check if it is null. If it is null, set it to 1. If it is not null, multiply it with the prev variable and update the element in the list.
Update the prev variable with the current element in the list.
Return the modified list.
Python3
def multiply_till_null(test_list): prev = 1 for i in range(len(test_list)): if not test_list[i]: test_list[i] = 1 else: test_list[i] *= prev prev = test_list[i] return test_list# initializing list of liststest_list = [1, 3, 4, False, 4, 5, False, 7, 8]# printing original listprint("The original list is:", test_list)# calling iterative functionresult = multiply_till_null(test_list)# printing modified listprint("The computed modified new list:", result) |
The original list is: [1, 3, 4, False, 4, 5, False, 7, 8] The computed modified new list: [1, 3, 12, 1, 4, 20, 1, 7, 56]
Time Complexity: O(n), where n is the length of the input list.
Auxiliary Space: O(1), as we are modifying the input list in-place and using a constant amount of extra space for the prev variable.
