Distinct n numbers so that sum equals to N

Question

Suppose I want to find n distinct numbers in the range from 1 to N, so that their sum is equal to N. e.g.

n = 3, N = 10: the numbers will be (2, 3, 5);
n = 4, N = 10: the numbers will be (1, 2, 3, 4).

While finding out all the possible combinations for this problem will take exponential time, I am looking for the "smallest" combination, i.e. the largest number is the smallest. For example,

in the case where n = 4, and N = 12, both (6, 3, 2, 1) and (5, 4, 2, 1) can be the solution, but I am only interested in (5, 4, 2, 1).

For this problem, will there be an algorithm with a better time complexity? I heard about the logarithmic merge, but not sure how that can be applied here.

If any details of the problem needs to be specified please let me know. And always, any help will be very much appreciated.

Answer 1

There is a simple greedy algorithm for this problem.

At first, there are n elements in ascending order, in order for them to be distinct, each element should be greater than its predecessor by at least one.

so, we have

1, 2, 3 ... , n

Now, the sum of all n number is n*(n + 1)/2

What is left is left = N - n*(n + 1)/2

In order to keep the last element as small as possible, we need to scatter the left difference to all numbers

so, we have

1 + left/n, 2 + left/n, ..., n + left/n

If left % n != 0, we just need to add extra 1 to the last left % n elements.

Note: if N < n*(n + 1)/2, there is no solution

Example:

So, for n = 4 and N = 12

First, we start with

1, 2, 3, 4

left = 12 - (4*5/2) = 2

So, now we have

1 + (2/4), 2 + (2/4), 3 + (2/4), 4 + (2/4) = 1, 2, 3, 4

As left % n = 2
Finally, we have

1, 2, 3 + 1, 4 + 1 = 1, 2, 4, 5

Similarly, for n = 3, N = 10

First, we start with

1, 2, 3

left = 10 - (3*4/2) = 4

So, now we have

1 + (4/3), 2 + (4/3), 3 + (4/3) = 2, 3, 4

As left % n = 1
Finally, we have

2, 3, 4 + 1 = 2, 3, 5

Pseudo-code, time complexity O(n)

int[]result = new int[n];
int left = N - n*(n + 1)/2;

for(int i = 0; i < n; i++){
    result[i] = i + 1 + left/n;
    if(i >= n - (left % n)){//Add extra one for last left % n elements
        result[i]++;
    }
}
return result;