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 discount to minimize their total cost. The discount is described as follows:
1. 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.
2. 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.
3. The customer can also choose to pay the amount `pairCost` for both the leftmost and rightmost books together. In this case, both books are removed. This option can be used at most k times.
Given the cost of books `cost`, the cost to purchase the leftmost and rightmost books together `pairCost`, and the maximum number of times the pairCost option can be applied `k`, find the minimum cost in which the customer can purchase all the books.
Example:
n = 3
cost = [1, 2, 3]
pairCost = 2
k = 1
All books are purchased optimally as follows:
- Buy book 1 and 3 using pairCost = 2
- Buy book 2 individually = 2
Total cost = 4
Constraints:
· 1 ≤ n ≤ 10⁵
· 1 ≤ pairCost ≤ 10⁹
· 1 ≤ k ≤ n
· 1 ≤ cost[i] ≤ 10⁹
· The cost array may not be sorted in any particular order.
Input Format for Custom Testing:
Sample Input:
5
9
11
13
15
17
6
2
Function:
- cost[] size n = 5
- cost = [9, 11, 13, 15, 17]
- pairCost = 6
- k = 2
Sample Output:
21
Explanation:
- Purchase the leftmost book individually: cost[0] = 9
- Purchase leftmost and rightmost books using pairCost = 6 (books 11 and 17)
- Purchase remaining books (13 and 15) individually or with pairCost depending on what's optimal
Total minimum cost = 21
Asked in: AMAZON
Image of the Question
All Testcases Passed ✔
