Amazon OA - Question 2 - Batch Packing

Round 2

Questions: There are n different types of products. You are given an array products of size n, where products[i] represents the number of items of product type i (where i ranges from 0 to n-1). These products need to be packed into batches for shipping.

Batch Packing Rules:

1. No two items in the same batch can be of the same product type, meaning all items in a batch must be of distinct types.
2. The number of items packed in the current batch must be strictly greater than the number packed in the previous batch.
3. Each item can be packed only once, and it is not required to pack every item.

Objective: Determine the maximum number of batches that can be prepared for shipment.

Example:

products = [2, 3, 1, 4, 2], n = 5 as there are 5 as len(products) = 5

Optimal Packing:

1. The first batch contains 1 item of product type 4. The remaining items: [2, 3, 1, 4, 1]
2. The second batch contains 2 items of product types 0 and 1. The remaining items: [1, 2, 1, 4, 1]
3. The third batch contains 3 items of product types 0, 1, and 3. The remaining items: [0, 1, 3, 1]
4. The fourth batch contains 4 items of product types 1, 2, 3, 4. The remaining items: [0, 0, 0, 2, 0]