Different Summands problem greedy alogrithm

Question

I try to solve Different Summands problem with greedy algorithm

Problem Description

Task. The goal of this problem is to represent a given positive integer 𝑛 as a sum of as many pairwise distinct positive integers as possible. That is, to find the maximum 𝑘 such that 𝑛 can be written as 𝑎1 + 𝑎2 + · · · + 𝑎𝑘 where 𝑎1, . . . , 𝑎𝑘 are positive integers and 𝑎𝑖 ̸= 𝑎𝑗 for all 1 ≤ 𝑖 < 𝑗 ≤ 𝑘.

Input Format. The input consists of a single integer 𝑛. Constraints. 1 ≤ 𝑛 ≤ 10^9.

Output Format. In the first line, output the maximum number 𝑘 such that 𝑛 can be represented as a sum of 𝑘 pairwise distinct positive integers. In the second line, output 𝑘 pairwise distinct positive integers that sum up to 𝑛 (if there are many such representations, output any of them).

My Code:

public class DifferentSummands {
    private static List<Integer> optimalSummands(int n) {
        List<Integer> summands = new ArrayList<Integer>();
        int start = 1;
        int newNumber = n;

        if (n == 2) {
            summands.add(2);
            return summands;
        }

        while (true) {
            if (summands.contains(newNumber - start)) {
                start++;
                continue;
            } else {
                newNumber -= start;
                summands.add(start);
                start++;
            }

            if (newNumber == 0) {
                return summands;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> summands = optimalSummands(n);
        System.out.println(summands.size());

        for (Integer summand : summands) {
            System.out.print(summand + " ");
        }
    }
}

My code fails if the input was so big it takes about 3.24 seconds and the max time available is 1.5 seconds.

Answer 1

after testing my code I find out the problem wasn't only in code performance but there are mistakes it code also but using HashSet was really nice it match faster than ArrayList and this is my new code

My code

private static HashSet<Integer> optimalSummands(int n) {
    HashSet<Integer> summands = new HashSet<>();
    int start = 1;
    int newNumber = n;
    if (n == 2) {
        summands.add(2);
        return summands;
    }

    while (true) {
        if (newNumber < 0) {
            Object[] value = summands.toArray();
            int secondlast = (int) value[summands.size() - 2];
            int last = (int) value[summands.size() - 1];

            summands.remove(last);
            summands.remove(secondlast);

            newNumber = secondlast + last -1;

        }
        if (summands.contains(newNumber - start) ) {
            start++;
            continue;
        } else {
            newNumber -= start;
            summands.add(start);
            start++;

        }

        if (newNumber == 0) {
            return summands;
        }
    }
}