Number of Ways to Buy Pens and Pencils

Medium

3 views

Topics:

Greedy Algorithms

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⁶

Number of Ways to Buy Pens and Pencils

Medium

3 views

Topics:

Greedy Algorithms

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⁶

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum possible values for totalMoney, penCost, and pencilCost? I want to understand the potential scale of the inputs.
Can totalMoney, penCost, or pencilCost ever be zero or negative?
If it's impossible to buy any combination of pens and pencils (e.g., totalMoney is less than both penCost and pencilCost), what should the function return?
Are we looking for the *number* of distinct combinations, or the *actual list* of combinations (which would have significant memory implications)?
Is integer overflow a potential concern given the number of ways we might find?

Brute Force Solution

Approach

The brute force approach to finding how many ways to buy pens and pencils is straightforward. We will consider every possible number of pens we can buy and, for each number of pens, calculate the number of pencils we can buy with the remaining money.

Here's how the algorithm would work step-by-step:

Start by trying to buy zero pens.
Check how many pencils you can buy with the remaining money.
Now, try buying one pen.
Again, check how many pencils you can buy with the remaining money.
Continue this process, increasing the number of pens you try to buy each time.
Stop when you can no longer afford to buy any more pens (when buying the next pen would require more money than you have).
For each number of pens you tried, you calculated the number of possible pencils you could also buy.
Add up all those pencil possibilities together. This gives you the total number of ways you can buy pens and pencils.

Code Implementation

def number_of_ways_to_buy_pens_and_pencils(total_money, pen_cost, pencil_cost):
    number_of_ways = 0
    max_pens_to_buy = total_money // pen_cost

    for number_of_pens in range(max_pens_to_buy + 1):

        # Calculate remaining money after buying pens.
        remaining_money = total_money - (number_of_pens * pen_cost)

        # Determine how many pencils we can buy.
        number_of_pencils_we_can_buy = remaining_money // pencil_cost

        # Each possible number of pens has a set of pencil possibilities.
        number_of_ways += number_of_pencils_we_can_buy + 1

    return number_of_ways

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(total) – The total amount of money is represented by the variable total. The algorithm iterates through all possible numbers of pens that can be bought, which is limited by total / cost1. For each possible number of pens, the algorithm calculates how many pencils can be bought with the remaining money using a division operation (total - i * cost1) / cost2. Because we iterate up to total/cost1 and inside each iteration the calculation is O(1), the dominant factor is the number of iterations, which is proportional to total. Therefore, the time complexity is O(total).

Space Complexity

O(1) – The provided solution iterates through possible numbers of pens and pencils without using any auxiliary data structures like arrays, lists, or hash maps to store intermediate results. It only uses a few variables (e.g., for loop counter, calculation of number of pencils). Since the number of variables used does not depend on the input values (money, penCost, pencilCost), the space complexity is constant.

Optimal Solution

Approach

The key idea is to directly calculate the number of ways to buy pencils for each possible number of pens. We can then sum up the number of ways across all possible numbers of pens. This avoids unnecessary iteration or complex calculations.

Here's how the algorithm would work step-by-step:

Figure out the maximum number of pens you can buy with the given money and pen cost. You can't buy a negative number of pens, so the minimum number of pens will be zero.
For each possible number of pens you *could* buy (starting from zero up to the maximum), calculate how much money is left over after buying that many pens.
With the leftover money, find out how many pencils you can buy. This will be the number of ways you can combine that specific number of pens with some number of pencils.
Add up the number of ways you can buy pencils for each possible number of pens. This sum is the total number of ways to buy pens and pencils.

Code Implementation

def number_of_ways_to_buy_pens_and_pencils(total_money, pen_cost, pencil_cost):    total_ways = 0
    #Determine max pens we can buy
    max_pens_can_buy = total_money // pen_cost

    for number_of_pens in range(max_pens_can_buy + 1):
        money_left_after_buying_pens = total_money - (number_of_pens * pen_cost)

        # Find out how many pencils we can buy with remaining money.
        number_of_pencils_we_can_buy = money_left_after_buying_pens // pencil_cost

        # Each pencil possibility forms a valid combination.
        total_ways += number_of_pencils_we_can_buy + 1

    return total_ways

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(money / penCost) – The time complexity is determined by the number of iterations in the main loop. The loop iterates from 0 up to the maximum number of pens that can be bought. This maximum is calculated by dividing the total money by the pen cost. Therefore, the loop runs approximately money / penCost times, making the time complexity O(money / penCost).

Space Complexity

O(1) – The provided solution calculates the number of ways to buy pencils based on the number of pens without using any auxiliary data structures that scale with the input. It only involves arithmetic calculations using a fixed number of variables to store the money, costs, and intermediate counts. Therefore, the space complexity is constant, independent of the input values. This constant space usage results in a space complexity of O(1).

Edge Cases

Case	How to Handle
totalMoney is zero	Return 1 because the only way to have 0 cost is to buy 0 pens and 0 pencils.
penCost or pencilCost is zero	If either cost is 0, calculate the maximum number of the other item and add 1 to the number of ways.
totalMoney is negative	Return 0 since negative money is not allowed
penCost or pencilCost is negative	Return 0 since negative cost is not allowed.
totalMoney is very large, potentially causing integer overflow during calculations	Use long data type to prevent overflow
penCost and pencilCost are both larger than totalMoney	Return 1 because the only way to meet conditions is to buy 0 pens and 0 pencils.
Either penCost or pencilCost is equal to totalMoney	Calculate total number of ways including buying only pens or only pencils.
Large totalMoney and small penCost/pencilCost, leading to a high number of combinations	Ensure the iterative or algorithmic approach is optimized to avoid time limit exceeded errors.