Maximum partitions of a number into unique integers in Java

To find the maximum k such that n can be written as :

a₁ + a₂ + · · · + a_k where a₁, . . . , a_k are positive and unique integers.

Given an integer n find maximum of partitions possibles.

Examples :

Input : 7
Output : 3
Explanation :
To maximize the partition of number n into k unique integers, we need
to start from minimum integer possible,i.e,1.
So, starting from 1, we take next integer 2, then 3, but sum of 1+2+3
= 6 and now only number possible is 1 but we have already included 1
so we cannot include 1 again.
Therefore, partition of 7 is 1,2,4.

Input : 50
Output : 9
Explanation :
Carrying on the above approach, we include 1,2,3,4,5,6,7,8 (sum = 36)
and now if we take 9, we will have to choose 5 but it's already
included, so we need to take 9 + 5 = 14 instead.
1+2+3+4+5+6+7+8+14 = 50.

As observed  from above examples, we always start from 1 and go till possible numbers such that sum of included numbers is equal to (k-1) first natural numbers and then last partition is (n-sum of included numbers).

The following algorithm takes an integer n and outputs maximum possible partitions k:

• So, we use sum of first k natural numbers,i.e,

\[\text{sum} = \dfrac{k(k+1)}{2}\]

• After rearranging terms, we get

\[k = \dfrac{-1 + \sqrt(1+8*sum)}{2}\]

• But due to casting from double to int, we will actually get k-1.
• So, we got k-1, we just need to add 1 and we get maximum numbers of partitions possible.

Below is the implementation of above algorithm :

/*package whatever //do not write package name here */

import java.io.*;

class Main {
    public static void main (String[] args) {
       int n1 = 50;
       int n2 = 100;
       maxPartsPossible(n1);
       maxPartsPossible(n2);
    }
  	private static void maxPartsPossible(int number){
	    int partitions = (int)((-1 + Math.sqrt(1+8*number))/2) - 1;
	    
	    System.out.println("Maximum Partitions : " + (partitions + 1));
	    
	}
}

As it is evident, partitions can also be printed pretty easily.

Print 1 to partitions(inclusive) and for the last partition, subtract sum of partitions natural number from n.

finalPartition = number – sumOfNaturalNo(partitions);