Maximum Number of Balls in a Box - Practice Coding Problems

Maximum Number of Balls in a Box - 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.

Input & Output

Example 1 — Small Range

$ Input: lowLimit = 1, highLimit = 10

› Output: 2

💡 Note: Balls 1,10 both go to box 1 (digit sum 1). Balls 2-9 each go to different boxes. Box 1 has maximum 2 balls.

Example 2 — Sequential Range

$ Input: lowLimit = 5, highLimit = 15

› Output: 2

💡 Note: Balls 5,14 both go to box 5 (5+0=5, 1+4=5). Ball 6→box6, 7→box7, etc. Box 5 has maximum 2 balls.

Example 3 — Same Digit Sum

$ Input: lowLimit = 19, highLimit = 28

› Output: 2

💡 Note: Balls 19,28 both go to box 10 (1+9=10, 2+8=10). Most other balls go to unique boxes.

Constraints

1 ≤ lowLimit ≤ highLimit ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Range

Ball numbers from lowLimit to highLimit

Calculate Digit Sums

Each ball goes to box number equal to sum of its digits

Count and Find Max

Return the box with most balls

Key Takeaway

🎯 Key Insight: Group balls by digit sum and count - the largest group gives the answer

Asked in

a Amazon 15 G Google 12

The key insight is to count balls per box using digit sums as keys. Calculate digit sum for each ball number and use hash map or array to count. Best approach is array counting since digit sums have limited range. Time: O(n×d), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass with Array	O(n × d)	O(1)	Use array instead of hash map for better performance since digit sums have small range
Hash Map Counting	O(n × d)	O(k)	Calculate digit sum for each ball number and count balls in each box

Single Pass with Array — Algorithm Steps

Create fixed-size array for box counts (max digit sum ~50)
Iterate through ball numbers once
For each ball, calculate digit sum and increment array count
Find maximum value in the count array

Visualization

Tap to expand

Step-by-Step Walkthrough

Fixed Array

Create array of size 50 for all possible digit sums

Direct Indexing

Use digit sum as direct array index

Linear Scan

Find maximum in single array pass

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int digitSum(int num) {
    int total = 0;
    while (num > 0) {
        total += num % 10;
        num /= 10;
    }
    return total;
}

int solution(int lowLimit, int highLimit) {
    int boxCount[50] = {0};
    
    for (int ball = lowLimit; ball <= highLimit; ball++) {
        int boxNum = digitSum(ball);
        boxCount[boxNum]++;
    }
    
    int maxCount = 0;
    for (int i = 0; i < 50; i++) {
        if (boxCount[i] > maxCount) {
            maxCount = boxCount[i];
        }
    }
    
    return maxCount;
}

int main() {
    int lowLimit, highLimit;
    scanf("%d", &lowLimit);
    scanf("%d", &highLimit);
    
    int result = solution(lowLimit, highLimit);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × d)

n iterations where n = highLimit - lowLimit + 1, and d digits per number to sum

✓ Linear Growth

Space Complexity

O(1)

Fixed-size array of ~50 elements regardless of input size

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass with Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler