FastPrep
Problem · Greedy

Minimal Cost to Increase Package Size

Learn this problem
● MediumAmazon logoAmazonOA
See Amazon hiring insights

Problem statement

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

minimalCostToIncreasePackageSize(size: int[], cost: int[]) → int

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

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
checking account