Maximum Number of Balls in a Box

Easy
554.

Maximum Number of Balls in a Box

Maximum Number of Balls in a Box is an easy coding problem on hash table, math and counting, asked in Amazon and Infosys interviews.

You have balls numbered lowLimit through highLimit and an unlimited number of boxes numbered from 1. Each ball goes into the box whose number equals the sum of the ball's digits — ball 321 goes to box 3 + 2 + 1 = 6.

Return the number of balls in the fullest box.

Example 1

Input
lowLimit = 1, highLimit = 10
Output
2
Explanation
Box 1 holds balls 1 and 10; every other box holds at most one.

Example 2

Input
lowLimit = 5, highLimit = 15
Output
2

Example 3

Input
lowLimit = 19, highLimit = 28
Output
2

Constraints

  • 1 <= lowLimit <= highLimit <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} lowLimit
 * @param {number} highLimit
 * @return {number}
 */
var countBalls = function(lowLimit, highLimit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Balls in a Box — Problem & Solution

Maximum Number of Balls in a Box solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Maximum Number of Balls in a Box is an easy coding problem on hash table, math and counting, asked in Amazon and Infosys interviews.

  • Difficulty: Easy
  • Topics: Hash Table, Math, Counting
  • Asked at: Amazon, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have balls numbered lowLimit through highLimit and an unlimited number of boxes numbered from 1. Each ball goes into the box whose number equals the sum of the ball's digits — ball 321 goes to box 3 + 2 + 1 = 6.

Return the number of balls in the fullest box.

Example 1

Input: lowLimit = 1, highLimit = 10
Output: 2
Explanation: Box 1 holds balls 1 and 10; every other box holds at most one.

Example 2

Input: lowLimit = 5, highLimit = 15
Output: 2

Example 3

Input: lowLimit = 19, highLimit = 28
Output: 2

Constraints

  • 1 <= lowLimit <= highLimit <= 100000

Hints for Maximum Number of Balls in a Box

  1. Hint 1

    The range is at most 100,000 balls, so iterating all of them is fine.

  2. Hint 2

    Digit sums here never exceed 45, so a small counting array suffices.

  3. Hint 3

    Track the maximum bucket as you fill it, avoiding a second pass.

How to solve Maximum Number of Balls in a Box

Bucket the balls by digit sum and report the largest bucket. Because the digit sum of a number below 100,000 is at most 45, the bucket space is tiny.

Approach

  1. For each ball number in the range, compute its digit sum with repeated % 10 and / 10.
  2. Increment that bucket's count.
  3. Track the running maximum count and return it.

Why it works

Every ball lands in exactly one box, so the bucket counts partition the range and the maximum bucket is the fullest box.

Complexity

  • Time — O((hi - lo) · log hi)
  • Space — O(1) — the digit-sum range is bounded by 45

Pitfalls

  • Starting the loop at 1 instead of lowLimit counts balls that were never placed.
  • Sizing the bucket array too small overflows: 99999 has digit sum 45, so 46 slots are needed.

Reference solution

Python

def countBalls(lowLimit: int, highLimit: int) -> int:
    boxes = [0] * 50
    best = 0
    for i in range(lowLimit, highLimit + 1):
        s = 0
        x = i
        while x > 0:
            s += x % 10
            x //= 10
        boxes[s] += 1
        if boxes[s] > best:
            best = boxes[s]
    return best

Java

public static int countBalls(int lowLimit, int highLimit) {
    int[] boxes = new int[50];
    int best = 0;
    for (int i = lowLimit; i <= highLimit; i++) {
        int s = 0, x = i;
        while (x > 0) { s += x % 10; x /= 10; }
        boxes[s]++;
        if (boxes[s] > best) best = boxes[s];
    }
    return best;
}

C++

int countBalls(int lowLimit, int highLimit) {
    vector<int> boxes(50, 0);
    int best = 0;
    for (int i = lowLimit; i <= highLimit; i++) {
        int s = 0, x = i;
        while (x > 0) { s += x % 10; x /= 10; }
        boxes[s]++;
        if (boxes[s] > best) best = boxes[s];
    }
    return best;
}

JavaScript

var countBalls = function(lowLimit, highLimit) {
    const boxes = new Array(50).fill(0);
    let best = 0;
    for (let i = lowLimit; i <= highLimit; i++) {
        let s = 0, x = i;
        while (x > 0) { s += x % 10; x = Math.floor(x / 10); }
        boxes[s]++;
        if (boxes[s] > best) best = boxes[s];
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets