Number of Ways to Buy Pens and Pencils

Med

#2040Time: O((total / cost1) * (total / cost2)) - In the worst-case scenario where `cost1` and `cost2` are 1, the complexity becomes O(total^2). Given `total` can be up to 10^6, this approach is too slow.Space: O(1) - We only use a few variables to store the counts and costs, so the space required is constant.1 company

Patterns

Math Enumeration

Companies

Prompt

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 <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible combination of the number of pens and pencils. We use two nested loops to iterate through all possible quantities of pens and pencils that could be bought individually. For each pair of quantities, we check if their combined cost is within the budget.

Algorithm

Initialize a counter variable ways to 0. This variable will store the total number of distinct ways.
Determine the maximum number of pens (maxPens) and pencils (maxPencils) that can be bought with the total money. maxPens = total / cost1 and maxPencils = total / cost2.
Start an outer loop to iterate through the number of pens i from 0 to maxPens.
Inside the outer loop, start a nested inner loop to iterate through the number of pencils j from 0 to maxPencils.
In the inner loop, calculate the total cost for the current combination: currentCost = i * cost1 + j * cost2.
Check if currentCost is less than or equal to total.
If the condition is true, it means this is a valid combination, so increment the ways counter.
After both loops complete, the ways variable will hold the total number of distinct ways. Return ways.

Walkthrough

The most straightforward way to solve this problem is to test every single combination of pens and pencils. We can set up two nested loops. The outer loop iterates through all possible numbers of pens, from 0 up to the maximum number of pens that can be afforded (total / cost1). The inner loop does the same for pencils, iterating from 0 up to total / cost2. Inside the inner loop, we calculate the total cost for the current combination of pens and pencils. If this total cost is within our budget (<= total), we count it as one valid way. Since the total number of ways can be very large, we must use a long data type for our counter to prevent potential integer overflow.

1class Solution {2    public long waysToBuyPensPencils(int total, int cost1, int cost2) {3        long ways = 0;4        long maxPens = total / cost1;5        long maxPencils = total / cost2;6 7        // Iterate through all possible numbers of pens8        for (long i = 0; i <= maxPens; i++) {9            // Iterate through all possible numbers of pencils10            for (long j = 0; j <= maxPencils; j++) {11                // Check if the total cost is within the budget12                if (i * cost1 + j * cost2 <= total) {13                    ways++;14                }15            }16        }17        return ways;18    }19}

Complexity

Time

O((total / cost1) * (total / cost2)) - In the worst-case scenario where `cost1` and `cost2` are 1, the complexity becomes O(total^2). Given `total` can be up to 10^6, this approach is too slow.

Space

O(1) - We only use a few variables to store the counts and costs, so the space required is constant.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for small inputs.

Cons

Extremely inefficient due to its quadratic time complexity.
Will not pass the given constraints and will result in a Time Limit Exceeded (TLE) error.

This approach improves upon the brute-force method by eliminating the inner loop. Instead of iterating through all pencil combinations for each pen combination, we can directly calculate the number of possible pencil combinations. We iterate through the number of pens one can buy and, for each count, calculate the remaining money. Then, we determine how many different quantities of pencils can be bought with this remaining amount.

Algorithm

Initialize a long counter variable ways to 0.
Loop through the number of pens, let's say numPens, starting from 0. The loop continues as long as the cost of pens (numPens * cost1) does not exceed total.
Inside the loop, for each numPens, calculate the money spent on pens: costOfPens = numPens * cost1.
Calculate the remaining money: remainingTotal = total - costOfPens.
With this remainingTotal, determine the number of ways to buy pencils. The maximum number of pencils that can be bought is k = remainingTotal / cost2. This allows for k + 1 choices for pencils (from 0 to k).
Add this number of choices (k + 1) to the ways counter.
After the loop finishes, ways will hold the total number of distinct combinations. Return ways.

Walkthrough

A more efficient method is to iterate through the possible quantities of just one item and calculate the possibilities for the second item directly. Let's choose to iterate through the number of pens.

For each possible number of pens, numPens, that we can afford, we calculate the cost and subtract it from our total money. This gives us the remainingTotal that can be spent on pencils. With this remainingTotal, the maximum number of pencils we can buy is remainingTotal / cost2. Since we can buy any number of pencils from 0 up to this maximum, there are (remainingTotal / cost2) + 1 ways to buy pencils for the given numPens.

We sum these ways for every possible value of numPens. The loop for numPens runs from 0 until numPens * cost1 exceeds total. It's crucial to use long for the ways counter and for intermediate calculations involving costs to prevent overflow.

To further optimize, we can iterate over the more expensive item. This reduces the number of iterations in the loop, making the solution faster, although the worst-case complexity remains the same.

1class Solution {2    public long waysToBuyPensPencils(int total, int cost1, int cost2) {3        long ways = 0;4        5        // Iterate through the number of pens6        for (int numPens = 0; (long)numPens * cost1 <= total; numPens++) {7            int remainingTotal = total - (numPens * cost1);8            9            // For the remaining money, calculate how many pencils can be bought.10            // If we can buy 'k' pencils, we can choose to buy 0, 1, ..., k pencils.11            // This gives k + 1 ways.12            long numPencilsWays = (long)(remainingTotal / cost2) + 1;13            ways += numPencilsWays;14        }15        16        return ways;17    }18}

Complexity

Time

O(total / cost1) - The loop runs `total / cost1 + 1` times. By iterating over the more expensive item, the complexity becomes O(total / max(cost1, cost2)). In the worst case (e.g., cost is 1), the complexity is O(total).

Space

O(1) - The algorithm uses a constant amount of extra space for variables, regardless of the input size.

Trade-offs

Pros

Significantly more efficient than the nested loop approach.
Passes the time limits for the given constraints.
Relatively simple to implement and understand.

Cons

The time complexity is linear with respect to total in the worst case, which might be a concern for extremely large inputs, although it's fine for the given constraints.

Solutions

Solution

1class Solution {2public3  long waysToBuyPensPencils(int total, int cost1, int cost2) {4    long ans = 0;5    for (int x = 0; x <= total / cost1; ++x) {6      int y = (total - x * cost1) / cost2 + 1;7      ans += y;8    }9    return ans;10  }11}

1class Solution {2public:3  long long waysToBuyPensPencils(int total, int cost1, int cost2) {4    long long ans = 0;5    for (int x = 0; x <= total / cost1; ++x) {6      int y = (total - x * cost1) / cost2 + 1;7      ans += y;8    }9    return ans;10  }11};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem