Problem Brief

Find Maximum Number of Batches

Given an array of products where each item is the quantity of some unique product, you need to ship these products in batches. The rules for creating a batch are as follows:

Each batch must contain only distinct products.
Each subsequent batch must contain strictly increasing number of distinct product types.

Find the maximum number of batches that can be created.

Function Description

Complete the function findMaximumNumberOfBatches in the editor.

findMaximumNumberOfBatches has the following parameter:

int[] products: an array of integers representing the quantity of each unique product

Returns

int: the maximum number of batches that can be created

1Example 1

Input

products = [2, 3, 4, 1, 2]

Output

Explanation

The maximum number of batches that can be created from the given products is 4. The remaining products after each batch are as follows:

After the first batch: [2, 3, 4, 1, 1]
After the second batch: [1, 2, 4, 1, 1]
After the third batch: [1, 1, 3, 0, 1]
After the fourth batch: [0, 0, 2, 0, 0]

Draft autosaves locally

public int findMaximumNumberOfBatches(int[] products) {
    // write your code here
}

Input

products

[2, 3, 4, 1, 2]

Output