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 sum till a K value, and again starts cumulation of sum from occurrence of K 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 sum of prev. value of list until K and restarts the procedure once a non K value is encountered.
Python3
# Python3 code to demonstrate # Chuncked summation every K value# using naive method # initializing list of liststest_list = [1, 3, 4, 10, 4, 5, 10, 7, 8]# printing original listprint ("The original list is : " + str(test_list))# initializing K K = 10# Chuncked summation every K 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] = 0# printing resultprint ("The computed modified new list : " + str(test_list)) |
The original list is : [1, 3, 4, 10, 4, 5, 10, 7, 8] The computed modified new list : [1, 4, 8, 18, 22, 27, 37, 44, 52]
Time Complexity: O(n), where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n), where n is the number of elements in the list “test_list”.
Method #2 : Using List Comprehension
In List Comprehenson, it creates a new list from an original list by adding each element to the sum of the K-1 previous elements. This is done using a list comprehension and the sum() function. The slice of the original list used to compute the sum starts from the maximum of 0 and i-K+1 to handle the first few elements, and ends at i+1 to include the current element. The new list is then printed.
Python3
# Python3 code to demonstrate # Chuncked summation every K value# using list comprehension# initializing list of liststest_list = [1, 3, 4, 10, 4, 5, 10, 7, 8]# initializing K K = 10# printing original listprint ("The original list is : " + str(test_list))# Chuncked summation every K value using list comprehensionnew_list = [sum(test_list[max(0, i-K+1):i+1]) for i in range(len(test_list))]# printing resultprint("The computed modified new list : " + str(new_list)) |
The original list is : [1, 3, 4, 10, 4, 5, 10, 7, 8] The computed modified new list : [1, 4, 8, 18, 22, 27, 37, 44, 52]
Time Complexity: O(n*m), where n is the length of the input list and m is the chunk size.
Auxiliary Space: O(n), as we need to create a new list of the same size as the input list
