Problem · Hash Table

Maximum Number of Packages

MediumAmazonNEW GRADOA
See Amazon hiring insights

In Amazon's online marketplace, the inventory manager is exploring strategies to enhance product sales. The focus is on creating appealing packages that offer customers a delightful shopping experience. To achieve this, the inventory manager aims to construct packages, each containing at most 2 items, to have an equal total cost across all packages. The total cost of a package is defined as the sum of the costs of the items contained within.

Task: Given an array cost of size n, representing the costs of individual items, determine the maximum number of packages that can be created, such that each package adheres to the constraint of having at most 2 items, and all packages have the same cost.

Note: Each item can be used in at most one package.

Constraints

1 ≤ n ≤ 2 x 105
1 ≤ cost[i] ≤ 2000

Examples
01 · Example 1
n = 3
cost = [2, 1, 3]
return = 2
Example 1 illustration
In the above example, it is only possible to create 1 package with cost 2, similarly only one package can have the cost 1, and two packages can have the cost 3. So, the answer is 2 (max pacakages with the same cost :)
Constraints
1 ≤ n ≤ 2 x 105
1 ≤ cost[i] ≤ 2000
More Amazon problems
drafts saved locally
public int maximumNumberOfPackages(int n, int[] cost) {
  // write your code here
}
n3
cost[2, 1, 3]
expected2
sign in to submit