CODEWITHSUNDEEP
javaalgorithmgreedy
Kero Fawzy
Kero Fawzy

Reputation: 700

Different Summands problem greedy alogrithm

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.

Upvotes: 0

Views: 2757

Answers (5)

ARPAN KUMAR NANDI
ARPAN KUMAR NANDI

Reputation: 31

My Code for this problem in Python.

def optimal_summands(n):

    if n <= 2:
        return [n]

    summands = []
    remainder = n

    j = 1
    while j <= remainder:
        remainder -= j

        if remainder <= j:
            summands.append(remainder + j)
            break

        summands.append(j)
        j += 1

    return summands


if __name__ == '__main__':
    n = int(input())
    summands = optimal_summands(n)
    print(len(summands))
    print(*summands)

Upvotes: 0

Kero Fawzy
Kero Fawzy

Reputation: 700

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;
        }
    }
}

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59323

The smallest number that can be made with at least k different summands is just the sum of all numbers from 1 to k. Any number smaller than that will have fewer summands... at most k-1.

Gauss has a formula for the sum of numbers from 1 to k. It's just k(k+1)/2.

You just need to find the largest k such that k(k+1)/2 <= n. From the above, you know that if k were any larger, then you could not divide n into that many summands, so this is the largest possible answer.

It's also very easy to actually generate k summands that add to n -- it's just the sum of all numbers from 1 to k-1, and then whatever is left over ( n - k(k-1)/2 ).

You can solve for k directly:

k(k+1)/2 <= n

kΒ² + k - 2n <=0

k <= (sqrt(8n+1)-1)/2

The last step is via the quadratic formula. Since you want the largest possible k, it's just

k = floor((sqrt(8n+1)-1)/2)

Upvotes: 4

Hanjoung Lee
Hanjoung Lee

Reputation: 2152

Even though we can solve it with HashSet, but we can without it.

We know that summands have consecutive numbers from 1 to start. So instead of checking the list, please note that if newNumber-start <= start then we must stop. So newNumber at this point should be the last number of our answer.

Revising your code accordingly with minimizing changes,

...
        while (true) {
            if (newNumber-start <= start) { // possibly (newNumber <= start*2)
                summands.add(newNumber);
                newNumber = 0;
            } else {
...

The overall time complexity is now O(n^0.5). (It was O(n) = O(n^0.5 * n^0.5) with List search)

Upvotes: 0

Imbar M.
Imbar M.

Reputation: 1114

When performing a contains on an ArrayList (summands variable), it goes through all the values in the list to find if the item is there already. O(n) operation.

Try using a HashSet instead of a list, for better performance O(1).

If you care about the order of items inside your result (summands) you could use a LinkedHashSet.

Upvotes: 1

Related Questions