Problem Description

Given two integers lowLimit and highLimit, you have a sequence of boxes numbered from 1 to infinity. Each box can contain balls, and you have one ball for every integer in the range [lowLimit, highLimit] (inclusive). For each number i in this range, you put a ball into the box with the number equal to the sum of the digits of i. For example, if i = 321, the sum of its digits is 3 + 2 + 1 = 6, so you put the ball into box 6.

Your task is to return the maximum number of balls in any box after all balls are distributed.

• Each ball is used exactly once (one per integer in the range).
• Boxes are indexed by the sum of digits of the numbers.
• Constraints: 1 ≤ lowLimit ≤ highLimit ≤ 10^5

Thought Process

To solve this problem, let's break down the requirements:

• For every integer between lowLimit and highLimit, compute the sum of its digits.
• Each sum represents a box number; increment the count for that box.
• After processing all numbers, find the box with the highest count.

Solution Approach

The problem can be solved efficiently with the following steps:

1. Initialize a counter:
   • Use a hash map or an array to keep track of the number of balls in each box, where the key is the digit sum (box number), and the value is the count of balls.
2. Iterate through the range:
   • For each number i from lowLimit to highLimit (inclusive), compute the sum of its digits.
   • Increment the count for the corresponding box in the counter.
3. Find the maximum:
   • After processing all numbers, find the maximum value in the counter, which represents the box with the most balls.

We use a hash map (or array) because it allows for quick lookups and updates. The digit sum calculation is straightforward and can be done in a helper function.

Example Walkthrough

Let's use lowLimit = 1 and highLimit = 10 as an example.

• Step 1: For each number from 1 to 10, compute the sum of digits:
• 1 → 1
• 2 → 2
• 3 → 3
• 4 → 4
• 5 → 5
• 6 → 6
• 7 → 7
• 8 → 8
• 9 → 9
• 10 → 1 + 0 = 1
• Step 2: Tally the balls in each box (sum of digits):
• Box 1: 2 balls (from 1 and 10)
• Boxes 2-9: 1 ball each
• Step 3: The maximum number of balls in any box is 2 (box 1).

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(N * D), where N = highLimit - lowLimit + 1 and D is the maximum number of digits (at most 5). For each number, we must sum its digits.
• Space Complexity: O(B), where B is the number of possible boxes (at most 45 for 5-digit numbers).

• Time Complexity: O(N * D), which is efficient since D is small (constant for this problem).
• Space Complexity: O(B), also very small.

Summary

The key to solving the "Maximum Number of Balls in a Box" problem is recognizing that the sum of the digits uniquely identifies the box for each ball. By counting how many times each digit sum occurs, we can efficiently determine the box with the most balls. The solution leverages simple iteration, digit sum calculation, and a hash map (or array) for counting, making it both intuitive and efficient.

Code Implementation

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        from collections import defaultdict
        box_counts = defaultdict(int)
        for i in range(lowLimit, highLimit + 1):
            digit_sum = 0
            n = i
            while n > 0:
                digit_sum += n % 10
                n //= 10
            box_counts[digit_sum] += 1
        return max(box_counts.values())
      

class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        unordered_map<int, int> boxCounts;
        for (int i = lowLimit; i <= highLimit; ++i) {
            int n = i, digitSum = 0;
            while (n > 0) {
                digitSum += n % 10;
                n /= 10;
            }
            boxCounts[digitSum]++;
        }
        int maxBalls = 0;
        for (auto &entry : boxCounts) {
            if (entry.second > maxBalls) {
                maxBalls = entry.second;
            }
        }
        return maxBalls;
    }
};
      

class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        Map<Integer, Integer> boxCounts = new HashMap<>();
        for (int i = lowLimit; i <= highLimit; i++) {
            int n = i, digitSum = 0;
            while (n > 0) {
                digitSum += n % 10;
                n /= 10;
            }
            boxCounts.put(digitSum, boxCounts.getOrDefault(digitSum, 0) + 1);
        }
        int maxBalls = 0;
        for (int count : boxCounts.values()) {
            maxBalls = Math.max(maxBalls, count);
        }
        return maxBalls;
    }
}
      

var countBalls = function(lowLimit, highLimit) {
    const boxCounts = {};
    for (let i = lowLimit; i <= highLimit; i++) {
        let n = i, digitSum = 0;
        while (n > 0) {
            digitSum += n % 10;
            n = Math.floor(n / 10);
        }
        boxCounts[digitSum] = (boxCounts[digitSum] || 0) + 1;
    }
    return Math.max(...Object.values(boxCounts));
};