Is Minimum Cost to Acquire Required Items easy or hard?

This problem is generally considered Medium difficulty. The implementation itself is simple, but identifying the correct greedy cases and reducing the search space to a few mathematical comparisons requires careful reasoning.

Minimum Cost to Acquire Required Items Python/Java solution

The greedy solution translates directly into code in Python, Java, C++, Go, or TypeScript. Each implementation calculates the cost for the relevant purchase cases and returns the minimum value. Because the algorithm is O(1), the implementation is short and efficient in all languages.

How to solve Minimum Cost to Acquire Required Items in O(1)?

Identify the pricing structure and derive the meaningful purchase cases. Calculate the total cost for scenarios such as buying all items individually, maximizing discounted bundles, or combining bundles with remaining single items. Compare these constant cases and return the minimum cost.

What is the best approach for Minimum Cost to Acquire Required Items?

Greedy case analysis is the most efficient approach. Instead of checking every possible purchase combination, you analyze the pricing rules and evaluate a few key scenarios such as buying items individually, using discounted bundles, or mixing both. Since the number of cases is constant, the final algorithm runs in O(1) time and O(1) space.

Is Minimum Cost to Acquire Required Items asked at Google/Amazon/Meta?

Problems involving cost minimization with greedy reasoning appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem number may vary, the pattern of analyzing pricing rules and choosing the cheapest combination is common in coding interviews.

What data structure is used in Minimum Cost to Acquire Required Items?

The solution typically does not require complex data structures. It relies on simple variables and arithmetic comparisons, combined with greedy reasoning and mathematical case analysis.

What is the time complexity of Minimum Cost to Acquire Required Items?

The optimal greedy solution runs in O(1) time because it evaluates only a small fixed number of purchase scenarios. Space complexity is also O(1) since the algorithm stores only a few variables for counts and costs.

Description Hints 3 Solution Video 12:27

3789. Minimum Cost to Acquire Required Items

Medium34.8% acceptance

You are given five integers cost1, cost2, costBoth, need1, and need2.

There are three types of items available:

An item of type 1 costs cost1 and contributes 1 unit to the type 1 requirement only.
An item of type 2 costs cost2 and contributes 1 unit to the type 2 requirement only.
An item of type 3 costs costBoth and contributes 1 unit to both type 1 and type 2 requirements.

You must collect enough items so that the total contribution toward type 1 is at least need1 and the total contribution toward type 2 is at least need2.

Return an integer representing the minimum possible total cost to achieve these requirements.

Example 1:

Input: cost1 = 3, cost2 = 2, costBoth = 1, need1 = 3, need2 = 2

Output: 3

Explanation:

After buying three type 3 items, which cost 3 * 1 = 3, the total contribution to type 1 is 3 (>= need1 = 3) and to type 2 is 3 (>= need2 = 2).
Any other valid combination would cost more, so the minimum total cost is 3.

Example 2:

Input: cost1 = 5, cost2 = 4, costBoth = 15, need1 = 2, need2 = 3

Output: 22

Explanation:

We buy need1 = 2 items of type 1 and need2 = 3 items of type 2: 2 * 5 + 3 * 4 = 10 + 12 = 22.
Any other valid combination would cost more, so the minimum total cost is 22.

Example 3:

Input: cost1 = 5, cost2 = 4, costBoth = 15, need1 = 0, need2 = 0

Output: 0

Explanation:

Since no items are required (need1 = need2 = 0), we buy nothing and pay 0.

Constraints:

1 <= cost1, cost2, costBoth <= 10⁶
0 <= need1, need2 <= 10⁹

Topics

Greedy Math

Hints open one at a time

Hint 1

First, use min(costBoth, cost1 + cost2) for min(need1, need2).

Hint 2

For the remaining type 1 requirement rem1, use cost min(costBoth, cost1) for the rest.

Hint 3

Do the same for type 2, using cost min(costBoth, cost2).

12:27

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minimumCost(self, cost1: int, cost2: int, costBoth: int, need1: int, need2: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Input

Input

Your code is saved on this device.Solution