Maximum Number of Balls in a Box — Problem & Solution
Maximum Number of Balls in a Box solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Number of Balls in a Box is an easy coding problem on hash table, math and counting, asked in Amazon and Infosys interviews.
- Difficulty: Easy
- Topics: Hash Table, Math, Counting
- Asked at: Amazon, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have balls numbered lowLimit through highLimit and an unlimited number of boxes numbered from 1. Each ball goes into the box whose number equals the sum of the ball's digits — ball 321 goes to box 3 + 2 + 1 = 6.
Return the number of balls in the fullest box.
Example 1
Input: lowLimit = 1, highLimit = 10
Output: 2
Explanation: Box 1 holds balls 1 and 10; every other box holds at most one.
Example 2
Input: lowLimit = 5, highLimit = 15
Output: 2
Example 3
Input: lowLimit = 19, highLimit = 28
Output: 2
Constraints
1 <= lowLimit <= highLimit <= 100000
Hints for Maximum Number of Balls in a Box
Hint 1
The range is at most 100,000 balls, so iterating all of them is fine.
Hint 2
Digit sums here never exceed 45, so a small counting array suffices.
Hint 3
Track the maximum bucket as you fill it, avoiding a second pass.
How to solve Maximum Number of Balls in a Box
Bucket the balls by digit sum and report the largest bucket. Because the digit sum of a number below 100,000 is at most 45, the bucket space is tiny.
Approach
- For each ball number in the range, compute its digit sum with repeated
% 10and/ 10. - Increment that bucket's count.
- Track the running maximum count and return it.
Why it works
Every ball lands in exactly one box, so the bucket counts partition the range and the maximum bucket is the fullest box.
Complexity
- Time —
O((hi - lo) · log hi) - Space —
O(1) — the digit-sum range is bounded by 45
Pitfalls
- Starting the loop at 1 instead of
lowLimitcounts balls that were never placed. - Sizing the bucket array too small overflows:
99999has digit sum 45, so 46 slots are needed.
Reference solution
Python
def countBalls(lowLimit: int, highLimit: int) -> int:
boxes = [0] * 50
best = 0
for i in range(lowLimit, highLimit + 1):
s = 0
x = i
while x > 0:
s += x % 10
x //= 10
boxes[s] += 1
if boxes[s] > best:
best = boxes[s]
return bestJava
public static int countBalls(int lowLimit, int highLimit) {
int[] boxes = new int[50];
int best = 0;
for (int i = lowLimit; i <= highLimit; i++) {
int s = 0, x = i;
while (x > 0) { s += x % 10; x /= 10; }
boxes[s]++;
if (boxes[s] > best) best = boxes[s];
}
return best;
}C++
int countBalls(int lowLimit, int highLimit) {
vector<int> boxes(50, 0);
int best = 0;
for (int i = lowLimit; i <= highLimit; i++) {
int s = 0, x = i;
while (x > 0) { s += x % 10; x /= 10; }
boxes[s]++;
if (boxes[s] > best) best = boxes[s];
}
return best;
}JavaScript
var countBalls = function(lowLimit, highLimit) {
const boxes = new Array(50).fill(0);
let best = 0;
for (let i = lowLimit; i <= highLimit; i++) {
let s = 0, x = i;
while (x > 0) { s += x % 10; x = Math.floor(x / 10); }
boxes[s]++;
if (boxes[s] > best) best = boxes[s];
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets