Given a List, the task is to write a Python program to perform grouping of sum till K occurs.
Examples:
Input : test_list = [2, 3, 5, 6, 2, 6, 8, 9, 4, 6, 1], K = 6
Output : [10, 6, 2, 6, 21, 6, 1]
Explanation : 2 + 3 + 5 = 10, grouped and cumulated before 6.
Input : test_list = [2, 3, 5, 6, 2, 6, 8], K = 6
Output : [10, 6, 2, 6, 8]
Explanation : 2 + 3 + 5 = 10, grouped and cumulated before 6.
Method : Using loop
In this, we maintain a sum counter, if K occurs the summation is appended to result list, along with K, else the summation counter is updated with current value.
Python3
# Python3 code to demonstrate working of# Group Sum till each K# Using loopfrom collections import defaultdict# initializing listtest_list = [2, 3, 5, 6, 2, 6, 8, 9, 4, 6, 1]# printing original listsprint("The original list is : " + str(test_list))# initializing KK = 6temp_sum = 0res = []for ele in test_list: if ele != K: temp_sum += ele # append and re initializing if K occurs else: res.append(temp_sum) res.append(ele) temp_sum = 0res.append(temp_sum)# printing resultprint("Computed list : " + str(res)) |
The original list is : [2, 3, 5, 6, 2, 6, 8, 9, 4, 6, 1] Computed list : [10, 6, 2, 6, 21, 6, 1]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method#2: Using Recursive method.
Algorithm:
- Initialize an empty list “res”, a temporary variable “temp_sum” to 0 and a variable “K” to the given value.
- Loop through each element in the input list “test_list”.
- If the current element is not equal to “K”, add it to “temp_sum”.
- If the current element is equal to “K”, append the current value of “temp_sum” to “res”, then append the current element “K” to “res”, and re-initialize “temp_sum” to 0.
- After the loop is complete, append the final value of “temp_sum” to “res”.
- Return the final list “res”.
Python3
def group_sum_recursive(test_list, K, temp_sum=0, res=[]): if not test_list: res.append(temp_sum) return res ele = test_list[0] if ele != K: temp_sum += ele else: res.append(temp_sum) res.append(ele) temp_sum = 0 return group_sum_recursive(test_list[1:], K, temp_sum, res)# initializing listtest_list = [2, 3, 5, 6, 2, 6, 8, 9, 4, 6, 1]# printing original listsprint("The original list is : " + str(test_list))# initializing KK = 6# getting computed list using recursionres = group_sum_recursive(test_list, K)# printing resultprint("Computed list : " + str(res)) |
The original list is : [2, 3, 5, 6, 2, 6, 8, 9, 4, 6, 1] Computed list : [10, 6, 2, 6, 21, 6, 1]
Time complexity: O(n), where n is the length of the input list “test_list”. The algorithm iterates through the list once.
Space complexity: O(n), where n is the length of the input list “test_list”. The algorithm creates a list of the same length as “test_list” to store the output. Additionally, the algorithm creates some constant space for temporary variables.
