CODEWITHSUNDEEP
pythonalgorithmgreedy
confused_programmer
confused_programmer

Reputation: 59

Different Summands problem - greedy alogrithm (Python)

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

Upvotes: 0

Views: 159

Answers (2)

ARPAN KUMAR NANDI
ARPAN KUMAR NANDI

Reputation: 31

Please try this solution, much simpler

def optimal_summands(n):

    if n <= 2:
        return [n]

    summands = []
    remainder = n

    j = 1
    while j <= remainder:
        remainder -= j

        if remainder <= j:
            summands.append(remainder + j)
            break

        summands.append(j)
        j += 1

    return summands


if __name__ == '__main__':
    n = int(input())
    summands = optimal_summands(n)
    print(len(summands))
    print(*summands)

Upvotes: 0

aropan
aropan

Reputation: 636

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

Upvotes: 1

Related Questions