Problem Statement

You are given an array of integers prices where each element prices[i] represents the number of coins required to buy the i^th fruit.

The fruit market has the following reward for each fruit:

• If you buy the i^th fruit for prices[i] coins, you can get the next (i + 1) fruits for free.

Note: Even if you have the option to take certain fruits for free, you can still choose to purchase them at their respective prices[j] to gain the reward for the next fruits.

Return the minimum number of coins needed to get all the fruits.

Examples

Example 1:

• Input: prices = [1, 6, 1, 2, 4]
• Expected Output: 2
• Explanation:
  • Purchase the first fruit for 1 coin. Get next i + 1 = 0 + 1 = 1 fruit for free.
  • Get a second fruit for free.
  • Purchase the third fruit for 1 coin, and get next i + 1 = 2 + 1 = 3 fruits for free.
  • Get fourth and fifth fruit for free.
  • Total cost = 1 + 1 = 2.

Example 2:

• Input: prices = [2, 3, 5, 1]
• Expected Output: 5
• Explanation:
  • Purchase the first fruit for 2 coins. This allows you to take the second fruit for free.
  • You get 2nd fruit for free, but still, purchase it with 3 coins to get the third and fourth fruit for free.
  • So, total cost = 2 + 3 = 5.

Example 3:

• Input: prices = [3, 2, 1, 4]
• Expected Output: 4
• Explanation:
  • Purchase the first fruit for 3 coins. Get next i + 1 = 0 + 1 = 1 fruit for free.
  • Get a second fruit for free.
  • Purchase the third fruit for 1 coin, and get next i + 1 = 2 + 1 = 3 fruits for free.
  • Get fourth fruit for free.
  • Total cost = 3 + 1 = 4.

Constraints:

• 1 <= prices.length <= 1000
• 1 <= prices[i] <= 10⁵

Try it yourself

Try solving this question here: