{x}
blog image

Maximum Number of Balls in a Box

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 <= 105

1742. Maximum Number of Balls in a Box

Problem Description

You are given two integers lowLimit and highLimit. You have balls numbered from lowLimit to highLimit (inclusive). Each ball is placed in a box numbered according to the sum of its digits. Find the box with the maximum number of balls.

Approach

The most straightforward approach is to simulate the process. For each ball number between lowLimit and highLimit, we calculate the sum of its digits. We use an array (or a hash map) to count how many balls are in each box. Finally, we find the maximum count among all boxes.

Since the maximum sum of digits for a number less than or equal to 105 is 45 (99999 -> 45), we can use an array of size 46 to store the counts.

Solution (Python3)

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        box_counts = [0] * 46  # Array to store counts for each box number
 
        for i in range(lowLimit, highLimit + 1):
            digit_sum = sum(int(digit) for digit in str(i))
            box_counts[digit_sum] += 1
 
        return max(box_counts)

Solution (Java)

import java.util.Arrays;
 
class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        int[] boxCounts = new int[46]; // Array to store counts for each box number
 
        for (int i = lowLimit; i <= highLimit; i++) {
            int digitSum = 0;
            int temp = i;
            while (temp > 0) {
                digitSum += temp % 10;
                temp /= 10;
            }
            boxCounts[digitSum]++;
        }
 
        return Arrays.stream(boxCounts).max().getAsInt();
    }
}

Solution (C++)

#include <vector>
#include <algorithm>
 
class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        std::vector<int> boxCounts(46, 0); // Vector to store counts for each box number
 
        for (int i = lowLimit; i <= highLimit; i++) {
            int digitSum = 0;
            int temp = i;
            while (temp > 0) {
                digitSum += temp % 10;
                temp /= 10;
            }
            boxCounts[digitSum]++;
        }
 
        return *std::max_element(boxCounts.begin(), boxCounts.end());
    }
};

Time and Space Complexity Analysis

Time Complexity: O(n * log10(m)), where n = highLimit - lowLimit + 1 and m = highLimit. The dominant operation is iterating through the numbers from lowLimit to highLimit and calculating the sum of digits for each. Calculating the sum of digits takes time proportional to the number of digits, which is approximately log10(m).

Space Complexity: O(1). The space used by the box_counts array is constant because its size is fixed at 46 (or a small constant), regardless of the input values.