#2240

Medium

LeetCode Problem Workspace

Number of Ways to Buy Pens and Pencils

Calculate all distinct ways to spend a fixed total on pens and pencils using a straightforward enumeration strategy.

Problem Statement

You have a fixed amount of money and the costs of a pen and a pencil. Determine all the distinct ways to spend the money on these items without exceeding the total. You may buy multiple units of either item or none at all.

Return the total number of unique combinations of pens and pencils that can be purchased. For example, with total = 20, cost1 = 10, and cost2 = 5, the output is 9 because enumerating each option for pens and matching pencils gives 9 valid purchase combinations.

Examples

Example 1

Input: total = 20, cost1 = 10, cost2 = 5

Output: 9

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

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 <= 106

Solution Approach

Enumerate by Fixing One Item

Iterate over the number of pens from 0 to total divided by pen cost. For each count, compute the maximum number of pencils that can be bought with the remaining money. Sum these counts to get the total number of combinations.

Use Integer Division to Limit Iterations

Calculate the maximum possible count for pens using integer division. This ensures the loop does not exceed valid bounds and each iteration directly counts valid pencil combinations efficiently.

Accumulate Total Combinations

For each fixed pen count, determine the number of pencil options and add to a running total. This method guarantees that all unique ways are included and avoids missing edge cases where one type is zero.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(total / min(cost1, cost2)) due to iterating over one item's possible quantities. Space complexity is O(1) since only counters are used, without storing all combinations explicitly.

What Interviewers Usually Probe

Does the candidate immediately recognize that a full enumeration is feasible given the problem constraints?
Are they correctly handling cases where one or both item costs exceed the total?
Do they calculate combinations without generating redundant states or unnecessary data structures?

Common Pitfalls or Variants

Common pitfalls

Failing to include the case where zero pens or zero pencils are purchased.
Using floating point division instead of integer division, causing off-by-one errors in counts.
Overcomplicating the solution with dynamic programming or arrays when simple math enumeration suffices.

Follow-up variants

Change the total to a very large number and see if enumeration still works efficiently with integer division optimization.
Introduce three items instead of two and discuss how enumeration scales or requires nested loops.
Modify the problem to maximize the number of items purchased instead of counting combinations, shifting from enumeration to optimization.

FAQ

What is the easiest way to calculate the number of ways to buy pens and pencils?

Fix the number of pens or pencils and compute the maximum number of the other item that can fit in the remaining total, summing all possibilities.

Can this problem be solved without loops?

No, enumeration is required to consider all combinations, though integer division can optimize the iteration limits.

How do you handle cases where the total is less than both item costs?

Only one combination is valid: buying zero pens and zero pencils.

Why is integer division important in this problem?

It ensures that the maximum number of items calculated does not exceed the total and avoids off-by-one errors.

Is this problem primarily a math or enumeration problem?

It combines both: math is used to compute limits for each item, and enumeration sums all valid combinations.

terminal

Solution

Solution 1: Enumeration

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{\textit{total} - x \times \textit{cost1}}{\textit{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.

1

2

3

4

5

6

7

class Solution:
    def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
        ans = 0
        for x in range(total // cost1 + 1):
            y = (total - (x * cost1)) // cost2 + 1
            ans += y
        return ans

Continue Practicing

#2249 count lattice points inside a circle #2310 sum of numbers with units digit k #2162 minimum cost to set cooking time