Scale Engineer

Maximum Number of Balls in a Box

Easy
#1595Time: 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).2 companies
Patterns
MathCounting
Data structures
Hash Table
Companies
Lucid MotorsAppDynamics

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

  • Initialize a HashMap<Integer, Integer> 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.

Walkthrough

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<Integer, Integer> 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.
import java.util.HashMap;import java.util.Map; class Solution {    public int countBalls(int lowLimit, int highLimit) {        Map<Integer, Integer> 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;    }}

Complexity

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).

Trade-offs

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.

Solutions

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();    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem