Positive Distinct Summands in Python

Question

This Code is giving wrong output for n=2 and it is very slow.

How Can i make this code for finding as many positive distinct summands more efficient?

TASK- Represent a given positive integer n as a sum of as many pairwise distinct positive integers as possible.

OUTPUT: First Contains an integer k.Second Line Contains k positive distinct positive summands that sum up to n.

Sample Input:

8

Output:

3

1 2 5

n=int(input())
p=[]
i=1
while(i<=n):
      if (n-i) not in p:
          p.append(i)
      n-=i
      i+=1
print(len(p))
print(*p)

Answer 1

You can solve the problem analytically. If the number you're trying to reach is N, then the answer will always be

1+2+3+ ... +n + r = N

where n is the largest possible number such that n < r. For example, take N=8, and consider the possible values of n

n   sum(1..n)  r
0       0      8
1       1      7
2     1+2=3    5
3    1+2+3=6   2    // too high, n is not less than r

Thus, when N is 8, n is 2 and r is 5, giving an answer of 1+2+5.

So the question becomes, given the value of N, how can we compute n. The first step is to note that the sum of 1 thru n is given by the equation

1+2+3+ ... +n = n(n+1)/2

Plug that into the first equation

n(n+1)/2 + r = N

Using the fact that n < r, we can rewrite this as

n(n+1)/2 + n < N

And that's the answer that you need to implement. For example, if N is 2, then the formula says n < 1 which means that n is 0 and r is 2. If N is 8, then n < 2.77, which means that n is 2 and r is 5.