FastPrep
Problem · Dynamic Programming

Get Min Cost

● MediumAmazonNEW GRADOA
See Amazon hiring insights

Amazon Kindle has several e-books that customers can purchase directly.

There are n books ordered sequentially numbered 1, 2,.., n, where the ith book has a cost of cost[i]. A customer wants to purchase all the books, and kindle offers the customer a unique scheme is described as the follows -

  • Let the leftmost book remaining in the sequence be book i. The customer can choose to buy the leftmost book individually for cost[i]. This book is then removed from the sequence.
  • Let the rightmost book remaining in the sequence be book j. The customer can choose to buy the rightmost book individually for cost[j]. This book is then removed from the sequence.
  • The customer can also choose to pay the amount pariCost for both the leftmost and rightmost books together. In this case, both the leftmost and rightMostbooks are removed. This option can be used as many as k times.

    • Given the cost of books cost, the cost to purchase the leftmost and rightmost books together, parCost, and the mx num of times the pairCost option can be applied k, find the min cost in which the customer can purchase all the books following the scheme above.

    Function Description

    Complete the function getMinCost in the editor.

    getMinCost has the following parameters:

    1. int cost[n]: the cost of each book
    2. int pairCost: the cost of purchase the leftmost and rightmost book together
    3. int k: the MAX NUM of times pairCost can be used

    Returns

    long int: the min cost to purchase all books

    Endless thanks to our best friend for their kind help in sharing the source!

    Examples
    01 · Example 1
    cost = [1, 2, 3]
pairCost = 2
k = 1
return = 3
    Example 1 illustration
    The min cost to purchase the books is 1 + 2 = 3. the ans is 3.
    02 · Example 2
    cost = [1, 1, 1]
pairCost = 2
k = 1
return = 3
    Purchase the books individually for 1 + 1 + 1 = 3. This new example test case was added on 07-03-2025. You can find relevant source image in the Problem Srouce section. My boundless thanks to the lovely friend who so kindly shared the resource!
    03 · Example 3
    cost = [9, 11, 13, 15, 17]
pairCost = 6
k = 2
return = 21
    Purchase the leftmost book. cost[0] = 9. Purchase the leftmost and rightmost for pairCost = 6. Purchase the leftmost and rightmost books for pairCost = 6. The total cost is 9 + 6 + 6 = 21. This new example test case was added on 07-03-2025. You can find relevant source image in the Problem Srouce section. My boundless thanks to the lovely friend who so kindly shared the resource!
    Constraints
  • 1 <= n <= 10^5
  • 1 ≤ pairCost ≤ 10^9
  • 1 ≤ k ≤ n
  • 1 <= cost[i] <= 10^9
  • The cost array may not be in increasing order
    • More Amazon problems
    drafts saved locally
    public long getMinCost(int[] cost, int pairCost, int k) {
  // write your code here
}
    cost[1, 2, 3]
    pairCost2
    k1
    expected3
    checking account