Minimum Number of Coins for Fruits II - Practice Coding Problems

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

Understanding the Visualization

Input

Array of fruit prices [3,1,2]

Purchase Strategy

Buy fruit 1 → get fruit 2 free, buy fruit 3

Output

Minimum cost: 4 coins

Key Takeaway

🎯 Key Insight: Each purchase creates a range of free fruits - optimize by considering all possible purchase combinations with dynamic programming

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

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n²)	O(n²)	Cache recursive results to avoid recomputation
Recursive Brute Force	O(2ⁿ)	O(n)	Try all possible ways to acquire fruits recursively
Bottom-Up Dynamic Programming	O(n²)	O(n²)	Build solution iteratively from smaller subproblems

Dynamic Programming with Memoization — Algorithm Steps

Define state as (position, free_until)
Use memoization table to cache results
For each position, try buying or taking free
Return cached result if already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

State

Define state as (position, free_until)

Cache

Store computed results in memo table

Lookup

Return cached result if state seen before

Code -

solution.c — C

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

#define MAX_STATES 100000

typedef struct {
    int pos;
    int freeUntil;
    int result;
} MemoEntry;

MemoEntry memo[MAX_STATES];
int memoSize = 0;

int findMemo(int pos, int freeUntil) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].pos == pos && memo[i].freeUntil == freeUntil) {
            return memo[i].result;
        }
    }
    return -1;
}

void addMemo(int pos, int freeUntil, int result) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].pos = pos;
        memo[memoSize].freeUntil = freeUntil;
        memo[memoSize].result = result;
        memoSize++;
    }
}

int solve(int pos, int freeUntil, int* prices, int n) {
    if (pos > n) {
        return 0;
    }
    
    int cached = findMemo(pos, freeUntil);
    if (cached != -1) {
        return cached;
    }
    
    int result = INT_MAX;
    
    // Option 1: Take for free if available
    if (pos <= freeUntil) {
        int val = solve(pos + 1, freeUntil, prices, n);
        if (val < result) result = val;
    }
    
    // Option 2: Buy current fruit
    int cost = prices[pos - 1];
    int newFreeUntil = (freeUntil > pos + pos) ? freeUntil : pos + pos;
    int val = cost + solve(pos + 1, newFreeUntil, prices, n);
    if (val < result) result = val;
    
    addMemo(pos, freeUntil, result);
    return result;
}

int solution(int* prices, int n) {
    memoSize = 0;
    return solve(1, 0, prices, n);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int prices[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prices[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(prices, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each of n positions with up to n different free_until values

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores n×n states plus recursion stack

⚠ Quadratic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler