You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive (i.e., n == highLimit - lowLimit + 1), and an infinite number of boxes numbered from 1 to infinity.
Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball's number. For example, the ball number 321 will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be put in the box number 1 + 0 = 1.
Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.
Example 1:
Input: lowLimit = 1, highLimit = 10 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 ... Ball Count: 2 1 1 1 1 1 1 1 1 0 0 ... Box 1 has the most number of balls with 2 balls.
Example 2:
Input: lowLimit = 5, highLimit = 15 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 ... Ball Count: 1 1 1 1 2 2 1 1 1 0 0 ... Boxes 5 and 6 have the most number of balls with 2 balls in each.
Example 3:
Input: lowLimit = 19, highLimit = 28 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 12 ... Ball Count: 0 1 1 1 1 1 1 1 1 2 0 0 ... Box 10 has the most number of balls with 2 balls.
Constraints:
1 <= lowLimit <= highLimit <= 105When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
Every ball number from the lower limit through the upper limit is examined once. Its decimal digits are added by peeling off the last digit repeatedly, and that sum selects the box whose tally increases. After the last ball is placed, the largest tally is the answer.
Here's how the algorithm would work step-by-step:
def countBalls(lowLimit, highLimit):
# A dictionary is used to represent the boxes, where each key is a digit sum and the value is the ball count.
box_counts = {}
# Iterate through each ball number from the start to the end limit.
for ball_number in range(lowLimit, highLimit + 1):
current_ball_number = ball_number
digit_sum = 0
while current_ball_number > 0:
digit_sum += current_ball_number % 10
current_ball_number //= 10
# This step places the ball in the correct box by incrementing the count for the calculated digit sum.
box_counts[digit_sum] = box_counts.get(digit_sum, 0) + 1
if not box_counts:
return 0
# After all balls are placed, find the maximum count among all the boxes.
return max(box_counts.values())The fast version performs the same placement walk from the lower limit through the upper limit. Each last digit is taken on its own and added into a running sum, and a missing box is treated as already holding zero so the first ball can be recorded in one update. The answer is still the largest stored tally.
Here's how the algorithm would work step-by-step:
from collections import defaultdict
def countBalls(lowLimit, highLimit):
# A dictionary is used to represent the boxes, mapping a digit sum to the count of balls.
box_counts = defaultdict(int)
# Iterate through each ball number to determine which box it belongs in.
for ball_number in range(lowLimit, highLimit + 1):
current_number = ball_number
digit_sum = 0
while current_number > 0:
digit = current_number % 10
digit_sum += digit
current_number //= 10
# Place the ball in the box corresponding to its digit sum by incrementing the count.
box_counts[digit_sum] += 1
# After sorting all balls, find the maximum count among all boxes.
if not box_counts:
return 0
return max(box_counts.values())| Case | How to Handle |
|---|---|
| The range contains a single ball | That ball occupies one box, so the fullest box contains one ball. |
| The range runs from one through ten | Ball ten has digit sum one and shares a box with ball one, so the highest count is two. |
| Two boxes tie for the most balls | The answer is the number of balls in either tied box, because only the count is required. |
| The lower limit equals the upper limit | Exactly one ball is placed, and the result is one. |
| A power of ten falls inside the range | Its digits sum to one, so it joins every other ball whose digits also sum to one. |
| Every ball has a different digit sum | Each occupied box holds one ball, and the maximum is one. |