Breaking an integer into the sum of pairwise distinct positive integers

Problem Description The goal of this problem is to represent

Problem

You are organizing a funny competition for children.

As a prize fund you have n candies, which you need to divide optimally among top k places in a competition such that:

1. A higher place receives a larger number of candies.
2. n candies are distributed among pairwise distinct positive integers.

The goal is to maximise k, i.e., calculate the maximum number of places (k) where distinct positive integers sum up to exactly n.

Examples

Example 1

Input: 6
Output: 3
Explanation: 6 can be represented as the sum of 1+2+3 (distinct integers).

Example 2

Input: 8
Output: 3
Explanation: 8 can be represented as the sum of 1+2+5 (distinct integers).

Solution

Method 1 - Greedy

Reasoning or Intuition

The problem is based on the concept of distributing a positive integer n as a sum of pairwise distinct integers:

• Start with small numbers (1, 2, ...) and keep adding them until it becomes impossible to distribute further without violating the restriction of distinct values.
• Reasoning: To make the sum maximally distinct, iteratively subtract small integers from n.

Approach

1. Start with k = 1.
2. Add integers (a1 = 1, a2 = 2, ...) until the remaining candies n are less than the next integer (k+1).
3. Add the difference (n - sum) to the last integer to ensure the sum equals n.

Code

C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void findMaxK(int n) {
        vector<int> result;
        int current = 1;
        
        while (n >= current) {
            result.push_back(current);
            n -= current;
            current++;
        }
        
        // Add remaining candies to the last number
        if (n > 0) {
            result.back() += n;
        }
        
        // Output the results
        cout << result.size() << endl;  // Output k
        for (int num : result) {
            cout << num << " ";
        }
        cout << endl;
    }
};

int main() {
    int n;
    cin >> n;
    Solution().findMaxK(n);
    return 0;
}

Java

import java.util.*;

public class Solution {
    public void findMaxK(int n) {
        List<Integer> result = new ArrayList<>();
        int current = 1;
        
        while (n >= current) {
            result.add(current);
            n -= current;
            current++;
        }
        
        // Add remaining candies to the last number
        if (n > 0) {
            result.set(result.size() - 1, result.get(result.size() - 1) + n);
        }
        
        // Output the results
        System.out.println(result.size()); // Output k
        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        new Solution().findMaxK(n);
    }
}

Python

class Solution:
    def find_max_k(self, n):
        result = []
        current = 1
        
        while n >= current:
            result.append(current)
            n -= current
            current += 1
        
        # Add remaining candies to the last number
        if n > 0:
            result[-1] += n
        
        # Output the results
        print(len(result))  # Output k
        print(" ".join(map(str, result)))  # Output the integers

# Input example
if __name__ == "__main__":
    n = int(input())
    Solution().find_max_k(n)

Complexity

• ⏰ Time complexity: O(sqrt(n)) The loop iterates approximately sqrt(n) times as the sum of k integers grows quadratically.
• 🧺 Space complexity: O(k) Space required to store the k numbers.