Categories
28°C, New York
Home Data Structures and Algorithms Find Minimum Number of Coins for Fruits II

Find Minimum Number of Coins for Fruits II

C/C++ Program for Greedy Algorithm to find Minimum number of Coins

Range Minimum Query (RMQ) in Python

Given a 1-indexed array prices[], where prices[i] represents the cost of the ith fruit in a store. The store has a special offer: if you buy the ith fruit for prices[i] coins, you can get the next i fruit for free.

Note: Even if you can get an fruit j for free, you still have the option to purchase it for prices[j] coins to receive a new offer. The task is to return the minimum number of coins needed to acquire all the fruits.

Examples:

Input: prices = [30, 10, 20]
Output: 40
Explanation:

  • Purchase the 1st fruit with 30 coins. Now, you are allowed to take the 2nd fruit for free, total coins = 30
  • Purchase the 2nd fruit with 1 coin. Now, you are allowed to take the 3rd fruit for free, total coins = 30 + 10 = 40.
  • Take the 3rd fruit for free, total coins = 40.

Input: prices = [2, 20, 2, 2]
Output: 4
Explanation:

  • Purchase the 1st fruit with 1 coin. Now, you are allowed to take the 2nd fruit for free, total cost = 2.
  • Take the 2nd fruit for free, total cost = 2.
  • Purchase the 3rd fruit for 1 coin. Now, you are allowed to take the 4th fruit for free, total cost = 2 + 2.
  • Take the 4th fruit for free, total cost = 4.

Approach: To solve the problem, follow the below idea:

The idea is to use the “take” and “nottake” approach of DP with memoization. When we take the ith fruit , we directly consider moving to fruits from i+1 to 2*i+2, skipping the next i fruits as per the offer. We recursively explore each valid move from these indices and find the minimum cost. Add the price of the current fruit to this minimum cost and return it. To optimize, we use a memoization vector initialized to zero to store the results of subproblems, ensuring we do not recompute values, improving efficiency.

Step-by-step algorithm:

  • Initialize a memoization array with default values set to – 1.
  • Base Case: If the current index exceeds the length, return 0.
  • Recursive Case: For each index, compute the total cost by taking the current fruit’s price and recursively solving for the next valid index (i + i + 1).
  • If the result is already computed, return it
  • Add the current fruit’s price to the minimum cost across all possible indices and return it.
  • Update the memoization array with the minimum cost for each index as you compute them.

Below is the implementation of the above algorithm:

C++ 
// C++ code
#include <bits/stdc++.h>
using namespace std;

// Recursive function to solve the problem
int solve(vector<int>& prices, int i, int n,
          vector<int>& dp)
{
    // If the index is out of bound, return 0 (base case)
    if (i >= n)
        return 0;
    // If the result is already computed previously, return
    // it
    if (dp[i] != -1)
        return dp[i];

    // Initialize the result as the maximum possible integer
    // value
    int ans = INT_MAX;

    // Iterate from the next item up to the 2*i+2-th item
    for (int j = i + 1; j <= 2 * i + 2; ++j) {
        // Recursively solve for the next valid index and
        // find the minimum result
        ans = min(ans, solve(prices, j, n, dp));
    }

    // Store the result in the memoization array and return
    // it
    return dp[i] = ans + prices[i];
}

// Function to find the minimum coins needed
int minimumCoins(vector<int>& prices)
{
    int n = prices.size();
    // Initialize the memoization vector with 0
    vector<int> dp(prices.size(), -1);
    return solve(prices, 0, n, dp);
}

int main()
{
    // Example input 1
    vector<int> prices1 = { 30, 10, 20 };
    cout << minimumCoins(prices1) << endl;

    // Example input 2
    vector<int> prices2 = { 2, 20, 2, 2 };
    cout << minimumCoins(prices2) << endl;

    return 0;
}
Java 
import java.util.*;

public class Main {

    // Recursive function to solve the problem
    public static int solve(List<Integer> prices, int i,
                            int n, int[] dp)
    {
        // If the index is out of bound, return 0 (base
        // case)
        if (i >= n)
            return 0;
        // If the result is already computed previously,
        // return it
        if (dp[i] != -1)
            return dp[i];

        // Initialize the result as the maximum possible
        // integer value
        int ans = Integer.MAX_VALUE;

        // Iterate from the next item up to the 2*i+2-th
        // item
        for (int j = i + 1; j <= 2 * i + 2; ++j) {
            // Recursively solve for the next valid index
            // and find the minimum result
            ans = Math.min(ans, solve(prices, j, n, dp));
        }

        // Store the result in the memoization array and
        // return it
        return dp[i] = ans + prices.get(i);
    }

    // Function to find the minimum coins needed
    public static int minimumCoins(List<Integer> prices)
    {
        int n = prices.size();
        // Initialize the memoization array with -1
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        return solve(prices, 0, n, dp);
    }

    public static void main(String[] args)
    {
        // Example input 1
        List<Integer> prices1 = Arrays.asList(30, 10, 20);
        System.out.println(minimumCoins(prices1));

        // Example input 2
        List<Integer> prices2 = Arrays.asList(2, 20, 2, 2);
        System.out.println(minimumCoins(prices2));
    }
}

// This code is contributed by Shivam
Python 
def solve(prices, i, n, dp):
    # Base case: If the index is out of bound, return 0
    if i >= n:
        return 0

    # If the result is already computed previously, return it
    if dp[i] != -1:
        return dp[i]

    # Initialize the result as the maximum possible integer value
    ans = float('inf')

    # Iterate from the next item up to the 2*i+2-th item
    for j in range(i + 1, min(2 * i + 2, n) + 1):
        # Recursively solve for the next valid index and find the minimum result
        ans = min(ans, solve(prices, j, n, dp))

    # Store the result in the memoization array and return it
    dp[i] = ans + prices[i]
    return dp[i]

def minimum_coins(prices):
    n = len(prices)
    # Initialize the memoization vector with -1
    dp = [-1] * n
    return solve(prices, 0, n, dp)

# Example input 1
prices1 = [30, 10, 20]
print(minimum_coins(prices1))  # Output: 40

# Example input 2
prices2 = [2, 20, 2, 2]
print(minimum_coins(prices2))  # Output: 4

#This code is contributed by rohit singh
JavaScript 
// Recursive function to solve the problem
function solve(prices, i, n, dp) {
    // If the index is out of bound, return 0 (base case)
    if (i >= n)
        return 0;
    // If the result is already computed previously, return it
    if (dp[i] !== -1)
        return dp[i];

    // Initialize the result as the maximum possible integer value
    let ans = Number.MAX_SAFE_INTEGER;

    // Iterate from the next item up to the 2*i+2-th item
    for (let j = i + 1; j <= 2 * i + 2; ++j) {
        // Recursively solve for the next valid index and find the minimum result
        ans = Math.min(ans, solve(prices, j, n, dp));
    }

    // Store the result in the memoization array and return it
    return dp[i] = ans + prices[i];
}

// Function to find the minimum coins needed
function minimumCoins(prices) {
    let n = prices.length;
    // Initialize the memoization array with -1
    let dp = new Array(prices.length).fill(-1);
    return solve(prices, 0, n, dp);
}

let prices1 = [30, 10, 20];
console.log(minimumCoins(prices1));

let prices2 = [2, 20, 2, 2];
console.log(minimumCoins(prices2));

Output
40
4

Time Complexity: O(n), where n is the number of fruits in the fruit market.
Auxiliary Space: O(n)



Tags:
#Uber #DSA #Dynamic Programming #Uber #Dynamic Programming

C/C++ Program for Greedy Algorithm to find Minimum number of Coins

Range Minimum Query (RMQ) in Python