Home > Net >  Different Summands problem - greedy alogrithm (Python)
Different Summands problem - greedy alogrithm (Python)

Time:01-02

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

CodePudding user response:

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
  • Related