What is the easiest way to calculate the number of ways to buy pens and pencils?

Fix the number of pens or pencils and compute the maximum number of the other item that can fit in the remaining total, summing all possibilities.

Can this problem be solved without loops?

No, enumeration is required to consider all combinations, though integer division can optimize the iteration limits.

How do you handle cases where the total is less than both item costs?

Only one combination is valid: buying zero pens and zero pencils.

Why is integer division important in this problem?

It ensures that the maximum number of items calculated does not exceed the total and avoids off-by-one errors.

Is this problem primarily a math or enumeration problem?

It combines both: math is used to compute limits for each item, and enumeration sums all valid combinations.

#2240

Medium

auto_awesome数学·结合·enumeration

LeetCode 题解工作台

买钢笔和铅笔的方案数

给你一个整数 total ，表示你拥有的总钱数。同时给你两个整数 cost1 和 cost2 ，分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱，去买任意数目的两种笔。请你返回购买钢笔和铅笔的不同方案数目。示例 1：输入： total = 20, cost1 = 10, co…

数学枚举

题目描述

给你一个整数 total ，表示你拥有的总钱数。同时给你两个整数 cost1 和 cost2 ，分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱，去买任意数目的两种笔。

请你返回购买钢笔和铅笔的 不同方案数目 。

示例 1：

输入：total = 20, cost1 = 10, cost2 = 5
输出：9
解释：一支钢笔的价格为 10 ，一支铅笔的价格为 5 。
- 如果你买 0 支钢笔，那么你可以买 0 ，1 ，2 ，3 或者 4 支铅笔。
- 如果你买 1 支钢笔，那么你可以买 0 ，1 或者 2 支铅笔。
- 如果你买 2 支钢笔，那么你没法买任何铅笔。
所以买钢笔和铅笔的总方案数为 5 + 3 + 1 = 9 种。

示例 2：

输入：total = 5, cost1 = 10, cost2 = 10
输出：1
解释：钢笔和铅笔的价格都为 10 ，都比拥有的钱数多，所以你没法购买任何文具。所以只有 1 种方案：买 0 支钢笔和 0 支铅笔。

提示：

1 <= total, cost1, cost2 <= 10⁶

lightbulb

解题思路

方法一：枚举

我们可以枚举购买钢笔的数量 $x$ ，对于每个 $x$ ，我们最多可以购买铅笔的数量为 $\frac{\textit{total} - x \times \textit{cost1}}{\textit{cost2}}$ ，那么数量加 $1$ 即为 $x$ 的方案数。我们累加所有的 $x$ 的方案数，即为答案。

时间复杂度 $O(\frac{total}{cost1})$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

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

speed

复杂度分析

指标	值
时间	complexity is O(total / min(cost1, cost2)) due to iterating over one item's possible quantities. Space complexity is O(1) since only counters are used, without storing all combinations explicitly.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate immediately recognize that a full enumeration is feasible given the problem constraints?
question_mark
Are they correctly handling cases where one or both item costs exceed the total?
question_mark
Do they calculate combinations without generating redundant states or unnecessary data structures?

warning

常见陷阱

外企场景

error
Failing to include the case where zero pens or zero pencils are purchased.
error
Using floating point division instead of integer division, causing off-by-one errors in counts.
error
Overcomplicating the solution with dynamic programming or arrays when simple math enumeration suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the total to a very large number and see if enumeration still works efficiently with integer division optimization.
arrow_right_alt
Introduce three items instead of two and discuss how enumeration scales or requires nested loops.
arrow_right_alt
Modify the problem to maximize the number of items purchased instead of counting combinations, shifting from enumeration to optimization.

help

常见问题

外企场景

继续练习

#2249 统计圆内格点数目 #2310 个位数字为 K 的整数之和 #2162 设置时间的最少代价