Maximum Number of Balls in a Box

Maximum Number of Balls in a Box

What is this problem about?

The Maximum Number of Balls in a Box coding problem gives you a range [lowLimit, highLimit] of ball numbers. Each ball goes into a box numbered by the digit sum of the ball's number. Find the maximum number of balls in any single box. For example, ball 25 goes to box 2+5=7.

Why is this asked in interviews?

AppDynamics, Accenture, and Lucid use this problem to test basic math and hash map usage. It evaluates whether candidates can compute digit sums efficiently and aggregate counts using a map. While simple, it tests clean code organization and correct digit sum computation — a common pattern in many interview problems.

Algorithmic pattern used

Digit sum + frequency counting: For each number from lowLimit to highLimit, compute its digit sum and increment a counter for that box. Return the maximum counter value. Digit sum computation is O(log n) per number. Total complexity: O((highLimit - lowLimit) * log(highLimit)).

For large ranges, note that the digit sum of numbers up to 10^5 is at most 9+9+9+9+9=45, so the hash map has at most 46 keys — very compact.

Example explanation

lowLimit = 1, highLimit = 10.

• Ball 1: box 1. Ball 2: box 2. ... Ball 9: box 9.
• Ball 10: digit sum = 1+0 = 1. Box 1.
• Box 1 has balls 1 and 10 → 2 balls.
• All other boxes have 1 ball each.
• Maximum = 2.

lowLimit = 5, highLimit = 15.

• Ball 5→5, 6→6, 7→7, 8→8, 9→9, 10→1, 11→2, 12→3, 13→4, 14→5, 15→6.
• Box 5: balls 5, 14 → 2. Box 6: balls 6, 15 → 2. Others: 1. Maximum = 2.

Common mistakes candidates make

• Incorrect digit sum for multi-digit numbers: A common mistake is summing only the first and last digit. Sum ALL digits.
• Off-by-one in range bounds: The range is inclusive [lowLimit, highLimit]. Using strict inequality excludes the boundary.
• Using a large fixed-size array: The maximum digit sum is bounded (e.g., 54 for 6-digit numbers). Use a small array or hash map, not an array of size highLimit.

Interview preparation tip

For the Math Hash Table Counting interview pattern, digit sum is a frequently used mapping function in interview problems. Memorize the clean digit sum loop: while n > 0: sum += n%10; n //= 10. Then apply frequency counting. This exact pattern appears in many "group numbers by property" interview questions.