Problem

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 thenumber of distinct ways you can buy some number of pens and pencils.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3

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^6

Solution

Method 1 – Enumeration (Brute Force)

Intuition

For each possible number of pens you can buy (from 0 up to total // cost1), calculate how many pencils you can buy with the remaining money. Sum over all possibilities.

Approach

  1. For each x from 0 to total // cost1 (number of pens), compute the remaining money.
  2. For each x, the number of pencils y can be from 0 to (total - x * cost1) // cost2.
  3. For each x, add (number of possible y) + 1 to the answer (the +1 is for y = 0).
  4. Return the total number of ways.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

func waysToBuyPensPencils(total, cost1, cost2 int64) int64 {
    var ans int64
    for x := int64(0); x*cost1 <= total; x++ {
        rem := total - x*cost1
        ans += rem/cost2 + 1
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

class Solution {
    fun waysToBuyPensPencils(total: Long, cost1: Long, cost2: Long): Long {
        var ans = 0L
        var x = 0L
        while (x * cost1 <= total) {
            val rem = total - x * cost1
            ans += rem / cost2 + 1
            x++
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
        ans = 0
        x = 0
        while x * cost1 <= total:
            rem = total - x * cost1
            ans += rem // cost2 + 1
            x += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn ways_to_buy_pens_pencils(total: i64, cost1: i64, cost2: i64) -> i64 {
        let mut ans = 0;
        let mut x = 0;
        while x * cost1 <= total {
            let rem = total - x * cost1;
            ans += rem / cost2 + 1;
            x += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    waysToBuyPensPencils(total: number, cost1: number, cost2: number): number {
        let ans = 0
        for (let x = 0; x * cost1 <= total; x++) {
            const rem = total - x * cost1
            ans += Math.floor(rem / cost2) + 1
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(total // cost1), since we iterate over all possible numbers of pens.
  • 🧺 Space complexity: O(1), only a few variables are used.