Python program to find the group sum till each K in a list

0 0 2 minutes read

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 loop
from collections import defaultdict
 
# initializing list
test_list = [2, 3, 5, 6, 2, 6, 8, 9, 4, 6, 1]
 
# printing original lists
print("The original list is : " + str(test_list))
 
# initializing K
K = 6
 
temp_sum = 0
res = []
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 = 0
 
res.append(temp_sum)
 
# printing result
print("Computed list : " + str(res))

Output

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 list
test_list = [2, 3, 5, 6, 2, 6, 8, 9, 4, 6, 1]
 
# printing original lists
print("The original list is : " + str(test_list))
 
# initializing K
K = 6
 
# getting computed list using recursion
res = group_sum_recursive(test_list, K)
 
# printing result
print("Computed list : " + str(res))

Output

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.