# Number of Ways to Buy Pens and Pencils
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-ways-to-buy-pens-and-pencils)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-buy-pens-and-pencils
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Companies:** [Reddit](https://scaleengineer.com/companies/reddit)
---
## 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 _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 <= 106`

# Approaches
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public long waysToBuyPensPencils(int total, int cost1, int cost2) {
        long ways = 0;
        long maxPens = total / cost1;
        long maxPencils = total / cost2;

        // Iterate through all possible numbers of pens
        for (long i = 0; i <= maxPens; i++) {
            // Iterate through all possible numbers of pencils
            for (long j = 0; j <= maxPencils; j++) {
                // Check if the total cost is within the budget
                if (i * cost1 + j * cost2 <= total) {
                    ways++;
                }
            }
        }
        return ways;
    }
}
```
### Algorithm
1. Initialize a counter variable `ways` to 0. This variable will store the total number of distinct ways.
2. 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`.
3. Start an outer loop to iterate through the number of pens `i` from 0 to `maxPens`.
4. Inside the outer loop, start a nested inner loop to iterate through the number of pencils `j` from 0 to `maxPencils`.
5. In the inner loop, calculate the total cost for the current combination: `currentCost = i * cost1 + j * cost2`.
6. Check if `currentCost` is less than or equal to `total`.
7. If the condition is true, it means this is a valid combination, so increment the `ways` counter.
8. After both loops complete, the `ways` variable will hold the total number of distinct ways. Return `ways`.

## Optimized Iteration with a Single Loop
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public long waysToBuyPensPencils(int total, int cost1, int cost2) {
        long ways = 0;
        
        // Iterate through the number of pens
        for (int numPens = 0; (long)numPens * cost1 <= total; numPens++) {
            int remainingTotal = total - (numPens * cost1);
            
            // For the remaining money, calculate how many pencils can be bought.
            // If we can buy 'k' pencils, we can choose to buy 0, 1, ..., k pencils.
            // This gives k + 1 ways.
            long numPencilsWays = (long)(remainingTotal / cost2) + 1;
            ways += numPencilsWays;
        }
        
        return ways;
    }
}
```
### Algorithm
1. Initialize a `long` counter variable `ways` to 0.
2. 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`.
3. Inside the loop, for each `numPens`, calculate the money spent on pens: `costOfPens = numPens * cost1`.
4. Calculate the remaining money: `remainingTotal = total - costOfPens`.
5. 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`).
6. Add this number of choices (`k + 1`) to the `ways` counter.
7. After the loop finishes, `ways` will hold the total number of distinct combinations. Return `ways`.

# Solutions
### Java

```java
class Solution {
public
  long waysToBuyPensPencils(int total, int cost1, int cost2) {
    long ans = 0;
    for (int x = 0; x <= total / cost1; ++x) {
      int y = (total - x * cost1) / cost2 + 1;
      ans += y;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long waysToBuyPensPencils(int total, int cost1, int cost2) {
    long long ans = 0;
    for (int x = 0; x <= total / cost1; ++x) {
      int y = (total - x * cost1) / cost2 + 1;
      ans += y;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```