Given a sum K then extracts distinct positive numbers that reach the sum.
Input : K = 17
Output : [1, 2, 3, 4, 7]
Explanation : List summation equals 17.Input : K = 21
Output : [1, 2, 3, 4, 11]
Explanation : List summation equals 21.
Method #1 : Using loop
In this, we take the smallest possible values that can reach K, for the last value, we subtract the remaining value from K from summed valued till the point.
Python3
# Python3 code to demonstrate working of# Distinct Positive Integers Sum to K# Using loop# initializing KK = 19# printing Kprint("The value of K : " + str(K))res = []idx = 0for ele in range(1, K): idx += ele # checking for last element point if K - idx < ele + 1: # appending initial elements res.extend(list(range(1, ele))) # appending last element left res.append(K - idx + ele) break# printing result print("The Required elements : " + str(res)) |
The value of K : 19 The Required elements : [1, 2, 3, 4, 9]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2 : Using combinations() + sum()
In this, we get the elements using combinations(), and check for sum using summation, this doesn’t perform in greedy but random way to get to the required summation.
Python3
# Python3 code to demonstrate working of# Distinct Positive Integers Sum to K# Using combinations() + sum()from itertools import combinations# initializing KK = 19# printing Kprint("The value of K : " + str(K))res = []flag = 0for idx in range(K - 1, 0, -1): # forming combinations for sub in combinations(range(1, K), idx): if sum(sub) == K and flag == 0: res.extend(list(sub)) flag = 1 break else: continue break# printing resultprint("The Required elements : " + str(res)) |
The value of K : 19 The Required elements : [1, 2, 3, 4, 9]
Time Complexity: O(n), where n is the length of the input list. This is because we’re using the built-incombinations() + sum() which has a time complexity of O(n) in the worst case.
Auxiliary Space: O(n), where n is the length of the input list as we’re using additional space other than the input list itself.
