You are given an integer total indicating the amount of money you have. You are also given two integers cost1 and cost2 indicating the price of a pen and pencil respectively. You can spend part or all of your money to buy multiple quantities (or none) of each kind of writing utensil.
Return the number of distinct ways you can buy some number of pens and pencils.
Example 1:
Input: total = 20, cost1 = 10, cost2 = 5 Output: 9 Explanation: The price of a pen is 10 and the price of a pencil is 5. - If you buy 0 pens, you can buy 0, 1, 2, 3, or 4 pencils. - If you buy 1 pen, you can buy 0, 1, or 2 pencils. - If you buy 2 pens, you cannot buy any pencils. The total number of ways to buy pens and pencils is 5 + 3 + 1 = 9.
Example 2:
Input: total = 5, cost1 = 10, cost2 = 10 Output: 1 Explanation: The price of both pens and pencils are 10, which cost more than total, so you cannot buy any writing utensils. Therefore, there is only 1 way: buy 0 pens and 0 pencils.
Constraints:
1 <= total, cost1, cost2 <= 106Problem Overview: You are given a total budget and the cost of a pen and a pencil. The task is to count how many different combinations of pens and pencils you can buy without exceeding the total amount. Any combination where the total cost is less than or equal to the budget is valid.
Approach 1: Brute Force Enumeration (Time: O((total/cost1) * (total/cost2)), Space: O(1))
The most direct solution enumerates every possible pair of pen and pencil counts. Iterate the number of pens from 0 to total / cost1. For each value, iterate the number of pencils from 0 to total / cost2 and check whether the combined cost stays within the budget. Each valid pair contributes one to the total count. This approach is straightforward and mirrors the problem statement, but the nested iteration becomes inefficient when the budget is large.
This method uses pure enumeration and basic arithmetic checks. It does not require additional data structures, so the space complexity stays constant. However, the time complexity grows quickly because every possible pair is tested. Problems involving counting combinations often start with this brute-force strategy before optimizing using insights from math or enumeration.
Approach 2: Mathematical Enumeration (Time: O(total/cost1), Space: O(1))
A more efficient approach avoids the inner loop entirely. Iterate the number of pens from 0 to total / cost1. For each choice of pens, compute the remaining budget as remaining = total - pens * cost1. The number of pencils you can buy is simply remaining / cost2. Since you can choose any pencil count from 0 up to that value, the number of valid combinations for this pen count is (remaining / cost2) + 1.
Add this value to the result for every possible pen count. This works because the pencil choices form a continuous range of valid values. Instead of checking each pair individually, you count all valid pencil options in constant time using integer division. The algorithm effectively enumerates only one dimension and derives the other mathematically.
This technique appears frequently in counting problems where one variable determines the remaining constraint for another variable. Recognizing this pattern turns a quadratic brute-force search into a linear scan based on simple arithmetic.
Recommended for interviews: The mathematical enumeration approach is what interviewers expect. Writing the brute-force solution first demonstrates that you understand the problem space. Then reducing the nested loop to a single loop using a formula shows stronger algorithmic reasoning and familiarity with optimization patterns common in counting and math-based problems.
In the brute force approach, we will iterate through possible numbers of pens starting from 0. For each feasible number of pens, we will calculate the leftover money and determine how many pencils we can buy with that remaining amount. We then sum the possibilities to get the total number of ways.
This C code iterates over possible numbers of pens while checking the remaining balance for pencils. The nested loop is simplified by realizing you can compute all pencil purchases from the remaining balance in one step.
The time complexity is O(total/cost1), where for each iteration, the inner calculation is O(1). The space complexity is O(1).
This approach eliminates the need for nested loops by utilizing a mathematical formula. For each number of pens, determine how many pencils can be bought by directly calculating based on the leftover money and their respective cost.
This solution exploits the same mathematical logic by summing possible pencils at each pen level, focusing on calculations over iterations.
The time complexity is O(total/cost1), and since calculations directly use arithmetic without further nesting, space complexity is O(1).
We can enumerate the number of pens to buy, denoted as x. For each x, the maximum number of pencils we can buy is \frac{total - x times cost1}{cost2}. The number of ways for each x is this value plus 1. We sum up the number of ways for all x to get the answer.
The time complexity is O(\frac{total}{cost1}), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(total/cost1), where for each iteration, the inner calculation is O(1). The space complexity is O(1). |
| Mathematical Formula Approach | The time complexity is O(total/cost1), and since calculations directly use arithmetic without further nesting, space complexity is O(1). |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O((total/cost1) * (total/cost2)) | O(1) | Useful for understanding the problem or very small constraints |
| Mathematical Enumeration | O(total/cost1) | O(1) | Optimal approach for large budgets; avoids nested loops using arithmetic counting |
2240. Number of Ways to Buy Pens and Pencils || Leetcode BiWeekly Contest 76 || Leetcode 2240 • Bro Coders • 1,441 views views
Watch 6 more video solutions →Practice Number of Ways to Buy Pens and Pencils with our built-in code editor and test cases.
Practice on FleetCode