Find Maximum Number of Batches
Updated
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, so a batch uses at most one unit of each product. Every unit is shipped in at most one batch.
- Each batch contains at least one product, and 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]
Constraints
1 <= n <= 10^5, wherenis the length ofproducts1 <= products[i] <= 10^9
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimum Distinct Prefix CostGoldman Sachs · OAGoldman Sachs interview questions
- Maximize Minimum Deployment DifficultyJP Morgan Chase · OAJP Morgan Chase interview questions
- Latest Arrival to Catch a BusAutodesk · OAAutodesk interview questions
- EV Charging Cost OptimizationTata Consultancy Services · OATata Consultancy Services interview questions
- Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions
- Minimum Removals to Balance ArraySalesforce · OASalesforce interview questions