Minimum Number of Coins for Fruits
You are given an 0-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the (i + 1)th fruit.
You are given an 0-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the (i + 1)th fruit.
The fruit market has the following reward for each fruit:
Note that even if you can take fruit j for free, you can still purchase it for prices[j - 1] coins to receive its reward.
Return the minimum number of coins needed to acquire all the fruits.
Example 1
Input: prices = [3,1,2]
Output: 4
Explanation: Note that even though you could take the 2 nd fruit for free as a reward of buying 1 st fruit, you purchase it to receive its reward, which is more optimal.
Example 2
Input: prices = [1,10,1,1]
Output: 2
Example 3
Input: prices = [26,18,6,12,49,7,45,45]
Output: 39
Explanation: Note that even though you could take the 6 th fruit for free as a reward of buying 3 rd fruit, you purchase it to receive its reward, which is more optimal.
Constraints
- 1 <= prices.length <= 1000
- 1 <= prices[i] <= 10^5
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.