Problem · Greedy

Minimal Cost to Increase Package Size

MediumAmazonOA
See Amazon hiring insights

One of the products listed on Amazon Ecommerce is available in n sizes as indicated in the array size. The category manager recognizes that some of the sizes are repetitive and do not provide a good user experience. To make the best use of inventory, the product should be available in distinct sizes.

The size of the i-th product, size[i], can be increased by one unit for an amount given in the cost array, cost[i]. In other words, increasing size[i] by k units costs cost[i] * k.

Given the arrays size and cost for the product, find the minimal total cost required to make all the sizes distinct.

Function Description

Complete the function minimalCostToIncreasePackageSize in the editor.

minimalCostToIncreasePackageSize has the following parameters:

  • int size[n]: an array of integers representing the sizes
  • int cost[n]: an array of integers representing the cost to increase each size by one unit

Returns

  • int: the minimal total cost to make all the sizes distinct
Examples
01 · Example 1
size = [2, 3, 2, 2]
cost = [2, 4, 5, 1]
return = 7
Given n = 4, size = [2, 3, 3, 2] and cost = [2, 4, 5, 1]. It costs 7 units to make the sizes distinct. We can also adjust size[1] to 5, which costs cost[1] * (5 - size[1]) = 8, and size[3] to 4, which costs cost[3] * (4 - size[3]) = 2, for a total of 8 + 2 = 10. However, 7 is the minimum cost required to make all sizes distinct.
Constraints
  • The arrays size and cost each contain n elements.
  • Each size size[i] may only be increased, never decreased.
  • Each increase changes a size by exactly one unit at a time, and each unit of increase to size[i] costs cost[i].
  • The goal is to make all values in size pairwise distinct at the minimum possible total cost.
More Amazon problems
drafts saved locally
public int minimalCostToIncreasePackageSize(int[] size, int[] cost) {
  // write your code here
}
size[2, 3, 2, 2]
cost[2, 4, 5, 1]
expected7
sign in to submit