FastPrep
Problem · Array

Find Maximum Number of Batches

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem 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:

  1. 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 = 4

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]

More Amazon problems

drafts saved locally
public int findMaximumNumberOfBatches(int[] products) {
    // write your code here
}
products[2, 3, 4, 1, 2]
expected4
checking account