Distinct n numbers so that sum equals to N

user_7798124 0
Viewed 3220

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.

algorithm
4 Answers

This can be calculated almost instantly. The answer will always either look like a run of numbers centered around N/n, or else a run of numbers with essentially the same center, with a gap of 1 somewhere in the middle.

So calculate that middle, then calculate whether and where you need that gap. Then you're done.

If n is odd, then the middle is N/n (assuming integer division) with enough shifted 1 to the right to account for the remainder. So, for example, if N is 10000 and n is 17, then the middle is 588, and your starting range is 588 ± (17-1)/2 which is 580-596. But the remainder is 4, so shift 4 over and and your answer will be 580-592, 594-597.

If n is the middle starts on a half number. So the middle is (N-n/2)/n + 0.5. So, for example, if N is 10000 and n is 18, then the middle is 555.5 and your starting range is 555.5 ± (18-1)/2 which is 547-564. But that division had a remainder of 1 so we get an answer of 547-563, 565.

user_5854110
Related