Skip to main content
Talentd

Minimum Cost to Acquire Required Items - Solution & Explanation

MediumMathGreedy8 min read
Practice this problem

Problem Statement

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 <= 106
  • 0 <= need1, need2 <= 109

Approach Overview

Problem Overview: You must acquire a required number of items while minimizing the total cost. The challenge comes from multiple purchase options or pricing rules, where certain combinations or purchase sizes change the effective cost. The goal is to determine the cheapest strategy that still satisfies the required quantity.

Approach 1: Brute Force Enumeration (O(k) time, O(1) space)

The most direct way is to enumerate all reasonable purchase combinations and compute the total cost for each. For example, if there are bundle sizes or alternative purchase rules, iterate through how many times you apply each option and calculate the remaining items that must be bought individually. Each configuration produces a total cost, and you keep track of the minimum. This approach works because the number of realistic combinations is small and bounded. The downside is unnecessary repeated calculations when many combinations lead to the same effective purchase pattern.

This method is useful for validating logic during development or when constraints are tiny. It also helps reveal patterns that lead to a more optimized solution. The time complexity is O(k), where k represents the number of candidate purchase strategies you test, and space complexity remains O(1) since only a few counters and cost variables are stored.

Approach 2: Greedy Case Analysis (O(1) time, O(1) space)

A more efficient method relies on observing how the pricing rules interact. Instead of testing every possibility, analyze the structure of the pricing and derive a small number of meaningful cases. For example, compare the cost of buying items individually versus buying them in discounted groups. If a bundle provides a cheaper per‑item rate, maximize its usage; otherwise prefer individual purchases. In some scenarios you evaluate a few boundary cases such as "all bundles", "all individual", or "bundles plus remainder".

This turns the problem into a small mathematical comparison. You compute the total cost for each candidate case and return the minimum. Since the number of cases is constant, the algorithm runs in O(1) time and O(1) space. This pattern frequently appears in problems combining greedy decision making with small math calculations, where a local price advantage determines the optimal strategy.

Recommended for interviews: Greedy case analysis. Interviewers expect you to reason about the pricing structure and reduce the solution to a few deterministic scenarios instead of brute forcing every combination. Showing the brute force idea demonstrates understanding, but identifying the mathematical cases proves you can simplify the search space and derive an optimal O(1) solution.

Solution

We can divide the purchasing strategy into three cases:

  1. Only buy Type 1 and Type 2 items. The total cost is a = need1 times cost1 + need2 times cost2.
  2. Only buy Type 3 items. The total cost is b = costBoth times max(need1, need2).
  3. Buy some Type 3 items, and purchase Type 1 and Type 2 items separately for the remaining needs. Let mn = min(need1, need2), then the total cost is c = costBoth times mn + (need1 - mn) times cost1 + (need2 - mn) times cost2.

Finally, we return the minimum value among the three cases, min(a, b, c).

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(k)O(1)When validating logic or when the number of possible purchase combinations is very small
Greedy Case AnalysisO(1)O(1)Preferred approach when pricing rules allow direct comparison between bundles and individual purchases

Video Solution

Minimum Cost to Acquire Required Items | LeetCode 3789 | Weekly Contest 482 • Sanyam IIT Guwahati • 678 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimum Cost to Acquire Required Items with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer