Taro Logo

Maximum Number of Balls in a Box

Easy
Asked by:
Profile picture
Profile picture
30 views
Topics:
Arrays

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

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Are the lower and upper limits both inclusive?
  2. Is each ball placed in the box numbered by the sum of its decimal digits?
  3. If two boxes hold the same number of balls, should the answer be that shared count?
  4. Do zeros inside a ball number add nothing to the sum while still counting as digits?
  5. What should be returned when the limits describe no balls at all?

Brute Force Solution

Approach

Every ball number from the lower limit through the upper limit is examined once. Its decimal digits are added by peeling off the last digit repeatedly, and that sum selects the box whose tally increases. After the last ball is placed, the largest tally is the answer.

Here's how the algorithm would work step-by-step:

  1. Create an empty mapping from digit sums to ball counts.
  2. Visit each ball number in the inclusive range.
  3. Split the number into decimal digits by taking remainders and dividing by ten.
  4. Add those digits to obtain the box number.
  5. Increase the count for that box, starting from zero when the box is new.
  6. Return zero when no balls were placed.
  7. Scan the recorded counts and return the largest one.

Code Implementation

def countBalls(lowLimit, highLimit):
    # A dictionary is used to represent the boxes, where each key is a digit sum and the value is the ball count.
    box_counts = {}

    # Iterate through each ball number from the start to the end limit.
    for ball_number in range(lowLimit, highLimit + 1):
        current_ball_number = ball_number
        digit_sum = 0
        while current_ball_number > 0:
            digit_sum += current_ball_number % 10
            current_ball_number //= 10

        # This step places the ball in the correct box by incrementing the count for the calculated digit sum.
        box_counts[digit_sum] = box_counts.get(digit_sum, 0) + 1

    if not box_counts:
        return 0

    # After all balls are placed, find the maximum count among all the boxes.
    return max(box_counts.values())

Big(O) Analysis

Time Complexity
O(n log m) – Let n be the number of balls in the inclusive range, and let m be the upper limit. Each ball is visited once, so the outer walk is linear in n. Pulling off digits divides the ball number by ten until nothing remains, and a number up to m has a logarithmic number of digits. The work per ball is therefore proportional to that digit count, which multiplies the linear walk by a logarithm of m. Looking up and later scanning the boxes adds only work proportional to the number of distinct sums, which is absorbed by the same bound, giving O(n log m) time.
Space Complexity
O(log m) – The mapping stores one entry for each digit sum that actually occurs. The largest possible digit sum is nine times the number of digits in the upper limit, so the number of entries grows logarithmically with m. The digit walk reuses a few counters and does not allocate per digit. The input is two limits rather than an explicit list of balls. The extra memory is O(log m).

Optimal Solution

Approach

The fast version performs the same placement walk from the lower limit through the upper limit. Each last digit is taken on its own and added into a running sum, and a missing box is treated as already holding zero so the first ball can be recorded in one update. The answer is still the largest stored tally.

Here's how the algorithm would work step-by-step:

  1. Create a mapping that treats a missing digit sum as a count of zero.
  2. Visit each ball number in the inclusive range.
  3. Take the last digit by itself and add it into the running sum.
  4. Remove that digit by dividing the remaining number by ten.
  5. Add one to the box selected by the finished sum.
  6. Return zero when the mapping is still empty.
  7. Scan every stored tally and return the maximum.

Code Implementation

from collections import defaultdict

def countBalls(lowLimit, highLimit):
    # A dictionary is used to represent the boxes, mapping a digit sum to the count of balls.
    box_counts = defaultdict(int)

    # Iterate through each ball number to determine which box it belongs in.
    for ball_number in range(lowLimit, highLimit + 1):
        current_number = ball_number
        digit_sum = 0
        while current_number > 0:
            digit = current_number % 10
            digit_sum += digit
            current_number //= 10
        
        # Place the ball in the box corresponding to its digit sum by incrementing the count.
        box_counts[digit_sum] += 1

    # After sorting all balls, find the maximum count among all boxes.
    if not box_counts:
        return 0
    return max(box_counts.values())

Big(O) Analysis

Time Complexity
O(n log m) – The number of balls n and the upper limit m are the same sizes as in the direct scan. Every ball is still processed once, and every ball still sheds one digit per division by ten. Treating a missing box as zero removes a separate existence branch, but that branch was constant work and does not change the leading term. The final scan of the boxes is proportional to the number of distinct digit sums, which is logarithmic in m. The total remains O(n log m).
Space Complexity
O(log m) – The default-zero mapping still stores only the digit sums that receive at least one ball. That collection cannot exceed a small multiple of the number of digits in m. No second copy of the ball range is kept. A handful of integer counters are reused for every ball. The extra memory is O(log m).

Edge Cases

The range contains a single ball
How to Handle:
That ball occupies one box, so the fullest box contains one ball.
The range runs from one through ten
How to Handle:
Ball ten has digit sum one and shares a box with ball one, so the highest count is two.
Two boxes tie for the most balls
How to Handle:
The answer is the number of balls in either tied box, because only the count is required.
The lower limit equals the upper limit
How to Handle:
Exactly one ball is placed, and the result is one.
A power of ten falls inside the range
How to Handle:
Its digits sum to one, so it joins every other ball whose digits also sum to one.
Every ball has a different digit sum
How to Handle:
Each occupied box holds one ball, and the maximum is one.