Shop in Candy Store

JavaView on GFG

Intuition

Buy k candies, for each bought candy get some free. Find min and max cost. Sort + greedy.

Algorithm

1Sort. Min cost: buy cheapest, get k freebies from most expensive. Max cost: buy most expensive, get freebies from cheapest.

Common Pitfalls

•Two greedy strategies. Min: pick from front, get free from back. Max: pick from back, get free from front.

Shop in Candy Store.java

Java

// Approach: Sort prices. Greedily: take cheapest free-k items as bought, then most expensive k as gifts.
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {
    public ArrayList<Integer> minMaxCandy(int[] prices, int k) {
        Arrays.sort(prices); // Sort prices in ascending order
        int n = prices.length;
        int start = 0, end = n - 1;

        // Minimum cost
        int minCost = 0;

        while (start <= end) {
            minCost += prices[start++]; // Buy cheapest
            end -= k; // Take k most expensive for free
        }

        // Maximum cost
        start = 0;
        end = n - 1;
        int maxCost = 0;
        while (start <= end) {
            maxCost += prices[end--]; // Buy most expensive
            start += k;
        }

        return new ArrayList<>(Arrays.asList(minCost, maxCost));
    }
}

Was this solution helpful?