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 = 5Output:9Explanation: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 = 10Output:1Explanation: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`

^{6}

**Solution: **

Enumerate all possible ways to buy k pens, e.g. 0 pen, 1 pen, …, total / cost1.

The way to buy pencils are (total – k * cost1) / cost2 + 1.

ans = sum((total – k * cost1) / cost2 + 1)) for k = 0 to total / cost1.

Time complexity: O(total / cost1)

Space complexity: O(1)

## C++

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