Pairwise Distinct Summands
This problem was taken from the Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 3:Greedy Algorithms, that I’ve recently completed. If you are taking that course or plan to take that course, please don’t look ahead at the solution as it will be against the Honor Code and won’t do you any good.
Problem Introduction
This is an example of a problem where a subproblem of the corresponding greedy algorithm is slightly distinct from the initial problem.
Problem Description
Task. The goal of this problem is to represent a given positive integer n as a sum of as many pairwise distinct positive integers as possible. That is, to find the maximum k such that n can be written as a(1) + a(2) + ··· + a(k) where a(1) ,…,a(k) are positive integers and a(i) != a(j) for all 1 ≤ i < j ≤ k.
Input Format. The input consists of a single integer n.
Constraints. 1 ≤ n ≤ 10^9
Output Format. In the first line, output the maximum number k such that n can be represented as a sum of k pairwise distinct positive integers. In the second line, output k pairwise distinct positive integers that sum up to n (if there are many such representations, output any of them).
Time Limits. C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit. 512 Mb
Sample 1
Input:
6
Output:
3
1 2 3
Sample 2
Input:
8
Output:
3
1 2 5
Sample 3
Input:
2
Output:
1
2
What To Do
To find an algorithm for this problem, you may want to play a little bit with small numbers. Assume, for example, that we want to represent 8 as a sum of as many pairwise distinct summands as possible. Well, it is natural to try to use 1 as the first summand, right? Then, the remaining problem is to represent 7 as a sum of the maximum number of pairwise distinct positive integers none of which is equal to 1. We then take 2 and are left with the following problem: represent 5 as a sum of distinct positive integers each of which is at least 3. Clearly, we cannot use two summands in this case (do you see why?). Overall, this gives us the following optimal representation:
8 = 1 + 2 + 5.
In general, our subproblem is the following: given integers k and l, where l ≤ k, represent k as a sum of as many pairwise distinct integers each of which is at least l as possible. If k ≤ 2l, then the answer is clearly 1. Otherwise it is safe to use l as one of the summands. Let’s state and prove this formally.
Lemma 5.1. Let k > 2l and let p be the maximum number such that k can be represented as a sum of p pairwise distinct summands each of which is at least l. Then there exists an optimal representation k = a(1) + ··· + a(p) (that is, all a(i) ’s are no smaller than l and are pairwise distinct) such that a(1) = l.
Proof. Consider some optimal representation k = b(1) + ··· + b(p) . Without loss of generality assume that b(1) < b(2) < … < b(p) . We know that p ≥ 2 (as k > 2l). If b(1) = l, then we are already done. Otherwise let ∆ = b(1) − l ≥ 1. Consider the following representation of n:
n = (b(1) − ∆) + b(2) + ··· + (b(p) + ∆).
It is not difficult to see that this is a valid and optimal representation (it contains p summands and they are all distinct since (b(1) − ∆) < b(2) < … < (b(p) + ∆))
It is not difficult to see that our initial problem has the same type: we need to represent an integer n as a sum of the maximum number of pairwise distinct integers each of which is at least 1 (hence k = n and l = 1).
To summarize, initially we have k = n and l = 1. To solve a (k,l)-sub-problem, we do the following. If k ≤ 2l, we output just one summand k. Otherwise we output l and then solve the sub-problem (k−l,l+1).
My Solution:
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.
