Problem · Array
Find Maximum Number of Batches
Learn this problem● Medium
AmazonOA
See Amazon hiring insightsAmazonOAProblem statement
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
findMaximumNumberOfBatches(products: int[]) → int
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
Examples
Example 1
products = [2, 3, 4, 1, 2]return = 4The 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]