# Maximum Number of Balls in a Box **Difficulty:** EASY [External](https://leetcode.com/problems/maximum-number-of-balls-in-a-box) Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-balls-in-a-box **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting) **Data structures:** Hash Table **Companies:** [Lucid Motors](https://scaleengineer.com/companies/lucid-motors), [AppDynamics](https://scaleengineer.com/companies/appdynamics) --- ## Problem 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` # Approaches ## Brute Force Simulation using HashMap This approach directly simulates the process described in the problem. We iterate through each ball number from `lowLimit` to `highLimit`. For each ball, we calculate the sum of its digits, which determines the box number. We use a HashMap to store the counts of balls in each box, where the key is the box number (digit sum) and the value is the count of balls. After processing all the balls, we find the maximum value stored in the HashMap to get the result. **Time:** O(N * log(H)), where N is the number of balls (`highLimit - lowLimit + 1`) and H is `highLimit`. The loop runs N times, and inside the loop, calculating the digit sum for a number `k` takes `O(log10(k))` time. · **Space:** O(K), where K is the number of unique box numbers. Given `highLimit <= 10^5`, the maximum number is `99999` and the maximum digit sum is `9*5 = 45`. Thus, K is at most 46, making the space complexity effectively O(1). **Pros:** Simple to understand and implement as it directly follows the problem statement.; Flexible, as it would work even if box numbers were not small, consecutive integers. **Cons:** Using a `HashMap` introduces overhead from hashing, boxing/unboxing integers, and managing the map structure, making it slightly less performant in practice compared to a simple array for this problem's constraints. ### Explanation This method is a straightforward translation of the problem statement into code. It's easy to understand but not the most performant due to the use of a `HashMap` where a simpler data structure would suffice. - **Algorithm Steps:** 1. Create a `HashMap` named `boxCounts` to map box numbers to ball counts. 2. Iterate with a variable `i` from `lowLimit` to `highLimit`. 3. Inside the loop, for each number `i`, calculate its digit sum. A helper function `getDigitSum(int n)` can be used, which repeatedly takes the number modulo 10 to get the last digit and adds it to a sum, then divides the number by 10, until the number becomes 0. 4. Let the calculated sum be `boxNum`. Update the count for this `boxNum` in the `boxCounts` map using `map.put(boxNum, map.getOrDefault(boxNum, 0) + 1)`. 5. While updating, we can also keep a running maximum to avoid a second pass over the map's values. 6. Return this maximum count. ```java import java.util.HashMap; import java.util.Map; class Solution { public int countBalls(int lowLimit, int highLimit) { Map boxCounts = new HashMap<>(); int maxBalls = 0; for (int i = lowLimit; i <= highLimit; i++) { int boxNum = getDigitSum(i); int currentCount = boxCounts.getOrDefault(boxNum, 0) + 1; boxCounts.put(boxNum, currentCount); if (currentCount > maxBalls) { maxBalls = currentCount; } } return maxBalls; } private int getDigitSum(int n) { int sum = 0; while (n > 0) { sum += n % 10; n /= 10; } return sum; } } ``` ### Algorithm - Initialize a `HashMap` to store the count of balls for each box number. - Loop through each ball number `i` from `lowLimit` to `highLimit`. - For each `i`, calculate the sum of its digits. This sum is the `boxNumber`. - A helper function `getDigitSum(int n)` can be used for this calculation. - Update the count for `boxNumber` in the HashMap. `map.put(boxNumber, map.getOrDefault(boxNumber, 0) + 1)`. - Keep track of the maximum count seen so far. - After the loop, the maximum count found is the answer. ## Simulation using an Array This approach is an optimization over the HashMap-based solution. Since the box numbers (digit sums) are small and fall within a predictable, narrow range, we can use a fixed-size array instead of a HashMap to store the ball counts. This avoids the overhead of hashing and object creation, leading to better performance due to direct memory access. **Time:** O(N * log(H)), where N is `highLimit - lowLimit + 1` and H is `highLimit`. The time complexity is asymptotically the same as the HashMap approach, but with a lower constant factor, making it faster in practice. · **Space:** O(1), as we use a fixed-size array (size 46) regardless of the input range. **Pros:** More efficient than the HashMap approach due to direct array indexing and avoiding object overhead.; Constant space complexity.; Still relatively simple to implement. **Cons:** Still involves re-calculating the digit sum from scratch for every number, which is not the most optimal way. ### Explanation By analyzing the constraints, we can see that the box numbers will be small. The maximum possible `highLimit` is `10^5`, so the largest number we might process is `99999`. The sum of its digits is `9+9+9+9+9 = 45`. This means all box numbers will be between 1 and 45. An array is a perfect data structure for this scenario. - **Algorithm Steps:** 1. Create an integer array `boxCounts` of size 46 (to have indices 0 through 45), initialized to zeros. 2. Iterate with a variable `i` from `lowLimit` to `highLimit`. 3. For each number `i`, calculate its digit sum, let's call it `boxNum`. 4. Increment the count for that box: `boxCounts[boxNum]++`. 5. After the loop finishes, iterate through the `boxCounts` array to find the maximum value. 6. Return this maximum value. ```java class Solution { public int countBalls(int lowLimit, int highLimit) { // Max possible sum for a number up to 10^5 (99999) is 9*5 = 45. // Array size 46 is sufficient (indices 0 to 45). int[] boxCounts = new int[46]; for (int i = lowLimit; i <= highLimit; i++) { int boxNum = 0; int temp = i; while (temp > 0) { boxNum += temp % 10; temp /= 10; } boxCounts[boxNum]++; } int maxBalls = 0; for (int count : boxCounts) { if (count > maxBalls) { maxBalls = count; } } return maxBalls; } } ``` ### Algorithm - Determine the maximum possible box number. For `highLimit <= 10^5`, the max sum is `9*5 = 45`. An array of size 46 is sufficient. - Create an integer array `boxCounts` of this size, initialized to zeros. - Iterate from `lowLimit` to `highLimit`. - For each number, calculate its digit sum (`boxNum`). - Increment the count in the array: `boxCounts[boxNum]++`. - After the loop, iterate through the `boxCounts` array to find the maximum value. - Return this maximum value. ## Optimized Simulation with Incremental Digit Sum This is the most efficient approach. It builds upon the array-based simulation but optimizes the calculation of the digit sum. Instead of re-calculating the sum for each number from scratch, it computes the digit sum of a number `i` based on the known digit sum of `i-1`. This clever trick avoids the expensive repeated division and modulo operations for every number, reducing the complexity of the inner operation to amortized constant time. **Time:** O(N + log(L)), where N is `highLimit - lowLimit + 1` and L is `lowLimit`. The initial sum calculation takes `O(log(L))`. The main loop runs N times. The work inside the loop is amortized O(1) because the `while` loop's total operations over the entire run are proportional to N. This simplifies to O(N). · **Space:** O(1), as we use a fixed-size array. **Pros:** Most efficient time complexity, `O(N)`.; Avoids redundant calculations by reusing the previous result.; Constant space complexity. **Cons:** The logic for updating the sum incrementally is slightly more complex to understand and implement compared to the straightforward calculation. ### Explanation The key observation is that `sum_digits(i)` is closely related to `sum_digits(i-1)`. - If `i-1` does not end in 9, then `sum_digits(i) = sum_digits(i-1) + 1`. (e.g., `sum(24)=6`, `sum(25)=7`). - If `i-1` ends in one or more 9s, a "carry" occurs. (e.g., from 29 to 30). `sum(29) = 11`, `sum(30) = 3`. The relationship is `sum(30) = sum(29) + 1 - 9`. For each trailing 9 in `i-1`, we effectively subtract 9 from the sum after the initial increment. - **Algorithm Steps:** 1. Create an integer array `boxCounts` of size 46. 2. Calculate the digit sum for `lowLimit` from scratch. Let's call it `currentSum`. Increment `boxCounts[currentSum]`. 3. Initialize a variable `maxBalls` to 1. 4. Iterate from `i = lowLimit + 1` to `highLimit`. 5. For each `i`, update `currentSum` based on the previous sum. Let `prev = i - 1`. 6. Increment `currentSum` by 1. 7. While `prev` ends in 9 (i.e., `prev % 10 == 9`), subtract 9 from `currentSum` and divide `prev` by 10 to check the next digit. 8. Increment `boxCounts[currentSum]`. 9. Update `maxBalls = Math.max(maxBalls, boxCounts[currentSum])`. 10. Return `maxBalls`. ```java class Solution { public int countBalls(int lowLimit, int highLimit) { int[] boxCounts = new int[46]; // Calculate sum for the first number int currentSum = 0; int temp = lowLimit; while (temp > 0) { currentSum += temp % 10; temp /= 10; } boxCounts[currentSum]++; int maxBalls = 1; // Iterate and calculate subsequent sums incrementally for (int i = lowLimit + 1; i <= highLimit; i++) { int prev = i - 1; currentSum++; // Increment for the last digit (e.g., from 24 to 25, sum goes from 6 to 7) // Adjust for carries (when previous number ends in 9) // e.g., from 29 to 30. sum(29)=11. currentSum becomes 12. 9 is a trailing digit. // currentSum -= 9 -> 3. which is sum(30). while (prev % 10 == 9) { currentSum -= 9; prev /= 10; } boxCounts[currentSum]++; if (boxCounts[currentSum] > maxBalls) { maxBalls = boxCounts[currentSum]; } } return maxBalls; } } ``` ### Algorithm - Create an integer array `boxCounts` of size 46. - Calculate the digit sum for `lowLimit` from scratch and store it as `currentSum`. Increment `boxCounts[currentSum]`. - Iterate from `i = lowLimit + 1` to `highLimit`. - To get the digit sum of `i`, start with the sum of `i-1`. Increment it by 1. - Then, adjust for any 'carries'. For every trailing 9 in `i-1`, subtract 9 from the sum. - This gives the new `currentSum` for number `i`. - Increment `boxCounts[currentSum]` and update the overall maximum count. - Return the maximum count after the loop. # Solutions ### CSharp ```csharp public class Solution { public int CountBalls(int lowLimit, int highLimit) { int[] cnt = new int[50]; for (int x = lowLimit; x <= highLimit; x++) { int y = 0; int n = x; while (n > 0) { y += n % 10; n /= 10; } cnt[y]++; } return cnt.Max(); } } ``` ### Java ```java class Solution { public int countBalls ( int lowLimit , int highLimit ) { int [] cnt = new int [ 50 ]; for ( int i = lowLimit ; i <= highLimit ; ++ i ) { int y = 0 ; for ( int x = i ; x > 0 ; x /= 10 ) { y += x % 10 ; } ++ cnt [ y ]; } return Arrays . stream ( cnt ). max (). getAsInt (); } } ``` ### JavaScript ```javascript /** * @param {number} lowLimit * @param {number} highLimit * @return {number} */ var countBalls = function ( lowLimit , highLimit ) { const cnt = Array ( 50 ). fill ( 0 ); for ( let i = lowLimit ; i <= highLimit ; ++ i ) { let y = 0 ; for ( let x = i ; x ; x = Math . floor ( x / 10 )) { y += x % 10 ; } ++ cnt [ y ]; } return Math . max (... cnt ); }; ``` ### CPP ```cpp class Solution { public: int countBalls ( int lowLimit , int highLimit ) { int cnt [ 50 ] = { 0 }; int ans = 0 ; for ( int i = lowLimit ; i <= highLimit ; ++ i ) { int y = 0 ; for ( int x = i ; x ; x /= 10 ) { y += x % 10 ; } ans = max ( ans , ++ cnt [ y ]); } return ans ; } }; ``` ### Python ```python class Solution : def countBalls ( self , lowLimit : int , highLimit : int ) -> int : cnt = [ 0 ] * 50 for x in range ( lowLimit , highLimit + 1 ): y = 0 while x : y += x % 10 x //= 10 cnt [ y ] += 1 return max ( cnt ) ```