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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3
4
5
6

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 <= 10^5

Solution

Method 1 – Hash Map Counting

Intuition

Each ball is placed in a box whose number is the sum of the digits of the ball’s number. We count how many balls go into each box and return the maximum count.

Approach

  1. Initialize a hash map (or array) to count balls in each box.
  2. For each ball number from lowLimit to highLimit:
    • Compute the sum of its digits.
    • Increment the count for that box.
  3. Track and return the maximum count among all boxes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        unordered_map<int, int> cnt;
        int ans = 0;
        for (int i = lowLimit; i <= highLimit; ++i) {
            int s = 0, x = i;
            while (x) {
                s += x % 10;
                x /= 10;
            }
            ans = max(ans, ++cnt[s]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func countBalls(lowLimit int, highLimit int) int {
    cnt := make(map[int]int)
    ans := 0
    for i := lowLimit; i <= highLimit; i++ {
        s, x := 0, i
        for x > 0 {
            s += x % 10
            x /= 10
        }
        cnt[s]++
        if cnt[s] > ans {
            ans = cnt[s]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0;
        for (int i = lowLimit; i <= highLimit; i++) {
            int s = 0, x = i;
            while (x > 0) {
                s += x % 10;
                x /= 10;
            }
            cnt.put(s, cnt.getOrDefault(s, 0) + 1);
            ans = Math.max(ans, cnt.get(s));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countBalls(lowLimit: Int, highLimit: Int): Int {
        val cnt = mutableMapOf<Int, Int>()
        var ans = 0
        for (i in lowLimit..highLimit) {
            var s = 0
            var x = i
            while (x > 0) {
                s += x % 10
                x /= 10
            }
            cnt[s] = cnt.getOrDefault(s, 0) + 1
            ans = maxOf(ans, cnt[s]!!)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        cnt: dict[int, int] = {}
        ans = 0
        for i in range(lowLimit, highLimit + 1):
            s = sum(int(d) for d in str(i))
            cnt[s] = cnt.get(s, 0) + 1
            ans = max(ans, cnt[s])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn count_balls(low_limit: i32, high_limit: i32) -> i32 {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        let mut ans = 0;
        for i in low_limit..=high_limit {
            let mut s = 0;
            let mut x = i;
            while x > 0 {
                s += x % 10;
                x /= 10;
            }
            let c = cnt.entry(s).or_insert(0);
            *c += 1;
            if *c > ans {
                ans = *c;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    countBalls(lowLimit: number, highLimit: number): number {
        const cnt: Record<number, number> = {};
        let ans = 0;
        for (let i = lowLimit; i <= highLimit; i++) {
            let s = 0, x = i;
            while (x > 0) {
                s += x % 10;
                x = Math.floor(x / 10);
            }
            cnt[s] = (cnt[s] || 0) + 1;
            ans = Math.max(ans, cnt[s]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n = highLimit - lowLimit + 1, since we process each ball once.
  • 🧺 Space complexity: O(1), since the number of possible digit sums is limited (at most 45 for 5-digit numbers).