What is the main pattern in the 'Maximum Number of Balls in a Box' problem?

The problem primarily uses a hash table to store counts for each box, while the sum of digits of each ball's number determines the box number.

How do I calculate the sum of digits for a ball number?

To calculate the sum of digits, repeatedly extract the last digit of the number by performing a modulus operation and add it to a running total. Then, divide the number by 10 and repeat until the number is reduced to zero.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of balls from lowLimit to highLimit, because we process each ball exactly once.

Can I solve this problem with a brute force approach?

Yes, but it may be inefficient for larger ranges. A more efficient solution uses a hash table to track ball counts and compute the sum of digits for each ball.

What are some potential optimizations for this problem?

You can optimize the solution by ensuring the sum of digits is computed efficiently and by using a hash table for constant time lookups and updates.

#1742

Easy

auto_awesome哈希·数学

LeetCode 题解工作台

盒子中小球的最大数量

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1 ）。另有无限数量的盒子，编号从 1 到 infinity 。你的工作是将每个…

哈希表数学计数

题目描述

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

示例 1：

输入：lowLimit = 1, highLimit = 10
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：2 1 1 1 1 1 1 1 1 0  0  ...
编号 1 的盒子放有最多小球，小球数量为 2 。

示例 2：

输入：lowLimit = 5, highLimit = 15
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：1 1 1 1 2 2 1 1 1 0  0  ...
编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。

示例 3：

输入：lowLimit = 19, highLimit = 28
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...
小球数量：0 1 1 1 1 1 1 1 1 2  0  0  ...
编号 10 的盒子放有最多小球，小球数量为 2 。

提示：

1 <= lowLimit <= highLimit <= 10⁵

lightbulb

解题思路

方法一：数组 + 模拟

观察题目的数据范围，小球的编号最大不超过 $10^5$ ，那么每个编号的各个位数之和的最大值小于 $50$ 。因此，我们可以直接开一个长度为 $50$ 的数组 $\textit{cnt}$ 来统计每个编号的各个位数之和的数量。

答案就是数组 $\textit{cnt}$ 中的最大值。

时间复杂度 $O(n \times \log_{10}m)$ 。其中 $n = \textit{highLimit} - \textit{lowLimit} + 1$ ，而 $m = \textit{highLimit}$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        cnt = [0] * 50
        for x in range(lowLimit, highLimit + 1):
            y = 0
            while x:
                y += x % 10
                x //= 10
            cnt[y] += 1
        return max(cnt)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate can identify the importance of using a hash table to store the count of balls in each box.
question_mark
Ensure the candidate understands the sum of digits concept and its relevance to the problem.
question_mark
Assess the candidate's ability to optimize the solution given the constraints, especially time complexity.

warning

常见陷阱

外企场景

error
Failing to efficiently compute the sum of digits for each number.
error
Not handling the edge cases, such as the smallest range (lowLimit = highLimit).
error
Using inefficient data structures that could increase time complexity unnecessarily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to consider larger ranges, forcing candidates to optimize the approach further.
arrow_right_alt
Introduce additional constraints on the ball or box numbers, requiring adjustments to the sum of digits logic.
arrow_right_alt
Allow multiple queries for different ranges and require a solution that can handle batch processing.

help

常见问题

外企场景

继续练习

#1814 统计一个数组中好对子的数目 #1512 好数对的数目 #1994 好子集的数目