Maximum Number of Balls in a Box

Difficulty: Easy | Acceptance: 74.90% | Paid: No Topics: Hash Table, Math, Counting

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 into the box whose number equals the sum of digits of the ball’s number. For example, ball 321 will be put into the box number 3 + 2 + 1 = 6 and ball 10 will be put into the box number 1 + 0 = 1.

Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.

• Examples
• Constraints
• Hash Map Counting
• Array-based Counting

Examples

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.

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.

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 <= 10^5

Hash Map Counting

Intuition Iterate through each ball number, calculate its digit sum, and use a hash map to track how many balls go into each box. The maximum value in the hash map is our answer.

Steps

• Initialize a hash map to store ball counts for each box
• Iterate from lowLimit to highLimit (inclusive)
• For each number, calculate the sum of its digits
• Increment the count for that digit sum in the hash map
• Track and return the maximum count found

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        count = {}
        max_balls = 0
        
        for num in range(lowLimit, highLimit + 1):
            digit_sum = 0
            n = num
            while n > 0:
                digit_sum += n % 10
                n //= 10
            
            count[digit_sum] = count.get(digit_sum, 0) + 1
            max_balls = max(max_balls, count[digit_sum])
        
        return max_balls

Complexity

• Time: O(n × d) where n = highLimit - lowLimit + 1 and d is the average number of digits
• Space: O(k) where k is the number of unique digit sums (at most 45)
• Notes: Hash map provides O(1) average case for insert and lookup operations

Array-based Counting

Intuition Since the maximum digit sum for any number up to 10⁵ is 45 (9+9+9+9+9), we can use a fixed-size array instead of a hash map for better performance and simpler code.

Steps

• Create an array of size 46 to store counts for all possible digit sums (0-45)
• Iterate from lowLimit to highLimit (inclusive)
• For each number, calculate the sum of its digits
• Increment the count at the index equal to the digit sum
• Track and return the maximum count found

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        count = [0] * 46
        max_balls = 0
        
        for num in range(lowLimit, highLimit + 1):
            digit_sum = 0
            n = num
            while n > 0:
                digit_sum += n % 10
                n //= 10
            
            count[digit_sum] += 1
            max_balls = max(max_balls, count[digit_sum])
        
        return max_balls

Complexity

• Time: O(n × d) where n = highLimit - lowLimit + 1 and d is the average number of digits
• Space: O(1) since array size is fixed at 46 regardless of input
• Notes: Array indexing is faster than hash map lookups and uses less memory overhead