Minimum Number of Coins for Fruits II - Problem

You are at a fruit market with different types of exotic fruits on display. You are given a 1-indexed array prices, where prices[i] denotes the number of coins needed to purchase the i-th fruit.

The fruit market has the following offer: If you purchase the i-th fruit at prices[i] coins, you can get the next i fruits for free.

Note that even if you can take fruit j for free, you can still purchase it for prices[j] coins to receive a new offer.

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

Input & Output

Example 1 — Basic Purchase Strategy

$ Input: prices = [3,1,2]

› Output: 4

💡 Note: Buy fruit 1 for 3 coins (get fruit 2 free), then buy fruit 3 for 2 coins. Total: 3 + 1 = 4 coins. Alternative: buy fruit 2 for 1 coin (get fruits 3-4 free, but fruit 4 doesn't exist), then buy fruit 1 for 3 coins. Total: 1 + 3 = 4 coins.

Example 2 — Optimal Free Fruits

$ Input: prices = [1,10,1,1]

› Output: 2

💡 Note: Buy fruit 1 for 1 coin (get fruit 2 free), then buy fruit 4 for 1 coin. Fruits 1 and 4 cost 1+1=2 coins, and fruit 2 is free from buying fruit 1, fruit 3 needs separate purchase but we can take it free by buying fruit 4 after taking fruit 2.

Example 3 — Single Fruit

$ Input: prices = [26]

› Output: 26

💡 Note: Only one fruit available, must buy it for 26 coins. No free fruits possible.

Constraints

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵
Array is 1-indexed for the problem logic

Visualization

Tap to expand

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is that each purchase decision creates a range of free fruits, and we need to find the optimal combination of purchases. The best approach uses dynamic programming with memoization to explore all states efficiently. Time: O(n²), Space: O(n²).

Common Approaches

✓ Bottom-Up Dynamic Programming

⏱️ Time: O(n²) Space: O(n²)

Use bottom-up DP where dp[i] represents minimum cost to acquire all fruits from position i to end. Work backwards from the last fruit.

Dynamic Programming with Memoization

⏱️ Time: O(n²) Space: O(n²)

Use memoization to store results of subproblems. Each state is defined by current position and how far free fruits extend.

Recursive Brute Force

⏱️ Time: O(2ⁿ) Space: O(n)

For each position, try buying the current fruit or taking it for free from previous purchases. Recursively explore all possibilities to find minimum cost.

Bottom-Up Dynamic Programming — Algorithm Steps

Initialize dp array
Work backwards from last fruit
For each position, consider buying or taking free
Return dp[1] for minimum cost

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set up DP table with base cases

Fill

Work backwards, computing optimal cost

Result

Answer is dp[1][0]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

static int dp[1001];

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* prices, int n) {
    // dp[i] = minimum cost to get all fruits from position i to end
    for (int i = 0; i <= n; i++) {
        dp[i] = INT_MAX;
    }
    dp[n] = 0;  // Base case: no more fruits
    
    // Fill DP table backwards
    for (int i = n - 1; i >= 0; i--) {
        // Try buying fruit i and getting next j fruits for free
        int maxJ = n;
        if (i + 1 + (i + 1) < n) {
            maxJ = i + 1 + (i + 1);
        }
        for (int j = i + 1; j <= maxJ; j++) {
            // Buy fruit i, get fruits i+1 to j-1 for free, solve for j onwards
            dp[i] = min(dp[i], prices[i] + dp[j]);
        }
        
        // Also try buying just fruit i and solve for i+1 onwards
        dp[i] = min(dp[i], prices[i] + dp[i + 1]);
    }
    
    return dp[0];
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int prices[1000];
    int n = 0;
    
    char* p = line;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        prices[n++] = (int)strtol(p, &p, 10);
    }
    
    int result = solution(prices, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position, may need to consider up to n different free ranges

✓ Linear Growth

Space Complexity

O(n²)

DP table with n positions and up to n different states per position

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Minimum Number of Coins for Fruits II - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler