I am trying to design a function called "distinct_summands" that takes in a positive integer n, to output a list of k distinct integers a1,..., ak such that a1+...+ak= n and k is as large as possible.
Some examples of the test cases are as follows: distinct_summands(8)=[1,2,5], distinct_summands(2)=[2], distinct_summands(14)=[1, 2, 3, 8]. I tested the codes myself for n=1,2,3...,100K. I didn't find any mistakes so far. However, when I submit the code to a black box code tester, I get an "out of index" error.
I tried everything I know to find out what went wrong. But I still don't know what went wrong. I attached my codes below. Can someone let me know what I did wrong?
def distinct_summands(n):
if n <=2:
return [n]
remainder = n
number_list = list(range(1, n+1))
prev_pos, curr_pos = 0, 0
summands = []
while remainder > number_list[prev_pos]:
remainder = remainder - number_list[curr_pos]
prev_pos = curr_pos
summands.append(number_list[prev_pos])
if remainder > 2* number_list[curr_pos+1]:
curr_pos += 1
else:
curr_pos = remainder -1
return summands
If n is large then number_list = list(range(1, n+1)) need a lot of memory (maybe it is cause out of index error). But you use the number_list array to get elements only, so I think you can replace number_list[index] to index + 1 and solve your problem:
def distinct_summands(n):
if n <= 2:
return [n]
remainder = n
prev_pos, curr_pos = 0, 0
summands = []
while remainder > prev_pos + 1:
remainder = remainder - (curr_pos + 1)
prev_pos = curr_pos
summands.append(prev_pos + 1)
if remainder > 2 * (curr_pos + 2):
curr_pos += 1
else:
curr_pos = remainder - 1
return summands