We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Coins for Fruits II

Number: 3268

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

You are given a 1-indexed array prices where prices[i] is the number of coins required to purchase the iᵗʰ fruit. When you purchase the iᵗʰ fruit you gain an “offer” – you may take the next i fruits for free. (In other words, buying fruit i “covers” the fruits in the interval [i, min(n, i+i)].) Note that even if a fruit is available for free you always have the option to purchase it in order to gain a new offer. Return the minimum number of coins needed so that you acquire all the fruits.

For example, in prices = [3,1,2]: • Buying the 1ˢᵗ fruit costs 3 coins and gives you fruit 2 for free. • Even though fruit 2 is free you may choose to buy it (for 1 coin) to get fruit 3 for free. The minimum total cost is 4 coins.

Key Insights

  • Think of a purchase at index j as “covering” fruits j through min(n, 2*j).
  • The overall problem is to “cover” the indices 1…n with such intervals.
  • Even if a fruit is available for free (i.e. already covered by a previous purchase) it might be optimal to purchase it if its price is low and its offer covers a larger range.
  • A useful recurrence is to define dp[i] as the minimum cost to have acquired fruits 1 through i. Notice that fruit i is acquired if it lies in the interval [j, 2*j] for some purchased fruit j.
  • In fact, one may show that for each i (1 ≤ i ≤ n) it holds that
      dp[i] = min { dp[j–1] + prices[j] } for j = ceil(i/2) … i
    because if fruit j was purchased then it “covers” fruits j through 2j (in particular i ≤ 2j must hold, equivalently j ≥ ceil(i/2)).
  • The naïve implementation of this recurrence is O(n²) but one may observe that for each i we want the minimum of A[j] = dp[j–1] + prices[j] over j in an interval [L, i] where L = ceil(i/2). This “range‐minimum query” can be answered in O(log n) time by a segment tree.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of fruits (using a segment tree for range minimum queries).
Space Complexity: O(n) for the dp array and the segment tree.

Solution

We first derive a recurrence for dp:
For i = 1…n, dp[i] is the minimum coins required to cover fruits 1 to i. Notice that if we purchase fruit j (1 ≤ j ≤ i) then fruit j and the next j fruits (up to index 2j) are acquired. Thus, i is “covered” if i ≤ 2j. In other words, in order for fruit j’s purchase to cover fruit i we must have j ≥ ceil(i/2). Hence the recurrence is

  dp[i] = min { dp[j – 1] + prices[j] } for all j in [ceil(i/2), i].

We then define an auxiliary array A where A[j] = dp[j – 1] + prices[j]. Once dp[0] is known (set to 0) we can “fill” dp[1…n] in increasing order. Since for each i we need the minimum A[j] over j in an interval [ceil(i/2), i] a segment tree (or similar structure) is used so that each query runs in O(log n) time. Finally, answer = dp[n].

Below are code solutions in four languages. Each solution uses a segment tree (with point‐updates and range minimum queries) so that the recurrence is computed efficiently.

Code Solutions

# Python solution with a segment tree for range-min queries.
import math
import sys

INF = 10**15  # a value larger than any possible dp value

class SegmentTree:
    def __init__(self, size):
        self.n = 1
        while self.n < size:
            self.n *= 2
        # initialize tree with INF
        self.tree = [INF] * (2 * self.n)
    
    def update(self, pos, value):
        # pos is 0-indexed; update leaf and then propagate.
        pos += self.n
        self.tree[pos] = value
        pos //= 2
        while pos:
            self.tree[pos] = min(self.tree[2*pos], self.tree[2*pos+1])
            pos //= 2
    
    def query(self, l, r):
        # returns min in [l, r) where l, r are 0-indexed.
        res = INF
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                res = min(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self.tree[r])
            l //= 2
            r //= 2
        return res

def minCoinsForFruits(prices):
    n = len(prices)
    dp = [INF] * (n+1)
    dp[0] = 0
    # We'll build an array A of size n+1.
    # A[j] = dp[j-1] + prices[j-1] (since prices is 0-indexed and fruits are 1-indexed).
    A = [INF] * (n+1)
    # Segment tree is built for indices 1..n (we use 0-indexing inside segment tree)
    seg = SegmentTree(n+1)
    # Special “free purchase” for fruit 1 is always allowed: update A[1]
    A[1] = dp[0] + prices[0]
    seg.update(1, A[1])
    
    for i in range(1, n+1):
        # Determine L = ceil(i/2). Because fruits are 1-indexed, use:
        L = (i + 1) // 2
        # Query segtree for min over indices [L, i] (inclusive). 
        # Our segment tree query is [l, r) so use r = i+1.
        candidate = seg.query(L, i+1)
        dp[i] = candidate
        if i < n:
            # Prepare candidate for fruit i+1: compute A[i+1] = dp[i] + prices[i]
            newVal = dp[i] + prices[i]
            # If a better value is found update the segment tree at position i+1.
            if newVal < A[i+1]:
                A[i+1] = newVal
                seg.update(i+1, newVal)
    return dp[n]

# Example usage:
if __name__ == '__main__':
    # Example 1:
    prices1 = [3, 1, 2]
    print(minCoinsForFruits(prices1))   # Expected output: 4

    # Example 2:
    prices2 = [1, 10, 1, 1]
    print(minCoinsForFruits(prices2))   # Expected output: 2
← Back to All Questions