Problem Description
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.
Key Insights
- You can buy any number of pens and pencils as long as the total cost does not exceed the available money.
- The maximum number of pens you can buy is limited by total / cost1.
- For each possible number of pens, calculate the remaining money and determine how many pencils can be bought with it.
- The number of valid purchases for pencils is determined by the remaining amount divided by the pencil's cost.
Space and Time Complexity
Time Complexity: O(total / cost1)
Space Complexity: O(1)
Solution
To solve this problem, we can use a straightforward iterative approach. We first calculate the maximum number of pens that can be purchased with the total amount of money. Then, for each possible number of pens from 0 to this maximum number, we compute the remaining money after buying those pens. Finally, we calculate how many pencils can be bought with the remaining money. The total number of distinct ways to buy pens and pencils is then the sum of all the ways to buy pencils for each possible number of pens.