LeetCode 2240 - Number of Ways to Buy Pens and Pencils

The problem asks us to determine the number of distinct ways to spend a given amount of money, total, on pens and pencils, each with fixed costs, cost1 for pens and cost2 for pencils.

leetcodemediummathenumeration

LeetCode Problem 2240

Difficulty: 🟡 Medium
Topics: Math, Enumeration

Solution

Problem Understanding

The problem asks us to determine the number of distinct ways to spend a given amount of money, total, on pens and pencils, each with fixed costs, cost1 for pens and cost2 for pencils. You can buy any non-negative number of each item, including zero, as long as the total cost does not exceed your budget.

The inputs are three positive integers: total, cost1, and cost2. The output is a single integer representing the number of unique combinations of pens and pencils that can be purchased.

Key observations from the constraints are that total, cost1, and cost2 can go up to 1,000,000, so any solution that iterates over all possible combinations naively (e.g., double loops for pens and pencils) could be too slow. Important edge cases include scenarios where the total is smaller than the cost of both items, which should result in only one valid combination: buying zero pens and zero pencils.

The problem guarantees all inputs are positive integers, so there is no need to handle zero or negative costs.

Approaches

The brute-force approach iterates over every possible number of pens you could buy (from 0 to total // cost1) and for each, iterates over every possible number of pencils that can fit within the remaining budget. This approach is guaranteed to produce the correct answer because it explicitly enumerates all valid combinations. However, it is inefficient: if total is large and cost1 and cost2 are small, the number of iterations could be on the order of millions, which could be too slow for LeetCode constraints.

The optimal approach uses a mathematical observation. For each possible number of pens, p, the maximum number of pencils you can buy is (total - p * cost1) // cost2. This means we only need a single loop iterating over possible pen counts, and for each, we compute the pencil count in constant time rather than using a nested loop. This reduces the time complexity significantly while still counting all valid combinations.

Approach Time Complexity Space Complexity Notes
Brute Force O(total / cost1 * total / cost2) O(1) Double loop over pens and pencils
Optimal O(total / cost1) O(1) Single loop over pens, compute pencils directly

Algorithm Walkthrough

  1. Initialize a variable ways to 0, which will store the total number of valid purchase combinations.
  2. Loop over every possible number of pens, num_pens, from 0 to the maximum possible (total // cost1). This ensures we consider all pen quantities that do not exceed the budget.
  3. For each num_pens, calculate the remaining money after buying pens: remaining = total - num_pens * cost1.
  4. Compute the maximum number of pencils that can be bought with the remaining money: max_pencils = remaining // cost2.
  5. Each combination of num_pens with 0 to max_pencils pencils is valid, so increment ways by max_pencils + 1.
  6. After finishing the loop, return ways.

Why it works: The algorithm enumerates all valid pen counts, and for each pen count, it directly calculates the range of valid pencil counts. This guarantees that all valid combinations are counted exactly once. The use of integer division ensures that we never exceed the budget.

Python Solution

class Solution:
    def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
        ways = 0
        max_pens = total // cost1
        for num_pens in range(max_pens + 1):
            remaining = total - num_pens * cost1
            max_pencils = remaining // cost2
            ways += max_pencils + 1
        return ways

The Python implementation follows the optimal approach. We first determine the maximum number of pens that can be bought. For each pen count, we calculate the remaining money and then determine how many pencils can fit in that remaining budget. Adding max_pencils + 1 accounts for all possible numbers of pencils, including zero.

Go Solution

func waysToBuyPensPencils(total int, cost1 int, cost2 int) int64 {
    var ways int64 = 0
    maxPens := total / cost1
    for numPens := 0; numPens <= maxPens; numPens++ {
        remaining := total - numPens*cost1
        maxPencils := remaining / cost2
        ways += int64(maxPencils + 1)
    }
    return ways
}

In Go, we use int64 for the result because the number of combinations can exceed int for large totals. The logic mirrors the Python solution, with explicit type conversions for safe arithmetic on large values.

Worked Examples

Example 1: total = 20, cost1 = 10, cost2 = 5

num_pens remaining max_pencils ways added cumulative ways
0 20 4 5 5
1 10 2 3 8
2 0 0 1 9

Result: 9

Example 2: total = 5, cost1 = 10, cost2 = 10

num_pens remaining max_pencils ways added cumulative ways
0 5 0 1 1

Result: 1

Complexity Analysis

Measure Complexity Explanation
Time O(total / cost1) We iterate only over the possible pen counts, which is at most total // cost1 + 1
Space O(1) We only use a few integer variables to store intermediate results

Since we avoid nested loops, the algorithm is efficient even for total up to 10^6.

Test Cases

# Provided examples
assert Solution().waysToBuyPensPencils(20, 10, 5) == 9  # multiple options
assert Solution().waysToBuyPensPencils(5, 10, 10) == 1  # cannot buy any

# Boundary values
assert Solution().waysToBuyPensPencils(1, 1, 1) == 2  # total is equal to cost
assert Solution().waysToBuyPensPencils(1_000_000, 1, 1) == 500001000001  # large total, small costs

# Only one type affordable
assert Solution().waysToBuyPensPencils(10, 5, 20) == 3  # only pens affordable
assert Solution().waysToBuyPensPencils(10, 20, 5) == 3  # only pencils affordable

# Both prices are higher than total
assert Solution().waysToBuyPensPencils(3, 5, 5) == 1  # can buy nothing
Test Why
20,10,5 Normal multiple purchase scenario
5,10,10 Cannot buy anything scenario
1,1,1 Minimal input
1_000_000,1,1 Stress test with maximum total
10,5,20 Only one item affordable
3,5,5 Both items too expensive

Edge Cases

  1. Cannot afford any item: When both cost1 and cost2 are larger than total, only the zero purchase is valid. The implementation correctly adds 1 for this case.
  2. Total divisible by one cost but not the other: This tests the correct integer division calculation to determine the number of pencils for each pen count. The algorithm calculates the maximum pencils using // to handle integer division correctly.
  3. Large total with small costs: The number of iterations can be very large. Using integer arithmetic ensures there is no floating-point precision issue and that memory usage remains constant. The Go version explicitly uses int64 to handle the large sum of combinations without overflow.