Leetcode 1742. Maximum Number of Balls in a Box

Problem Description

In this problem, you are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive. For example, if lowLimit = 1 and highLimit = 10, you have 10 balls numbered from 1 to 10.

You are supposed to put each ball in a box whose number is equal to the sum of the digits of the ball's number. For instance, the ball numbered 321 would go into box number 3 + 2 + 1 = 6, and the ball numbered 10 would go into box number 1 + 0 = 1.

Given two integers lowLimit and highLimit, you need to return the number of balls in the box with the most balls.

Approach

We can use a counter to store the number of balls in each box. For each ball, find the sum of its digits and increment the count corresponding to that box. Keep track of the maximum count while iterating through the balls.

Since the maximum value for highLimit is 10^5, the maximum sum of digits for a number would be around 9 + 9 + 9 + 9 + 9 = 45 (i.e., 99,999). Therefore, we can initialize an array of size 46 to store the count of each box.

Example Walkthrough

Let us walk through example input lowLimit = 5 and highLimit = 15.

1. Initialize an array count of size 46 with all elements as 0.

2. Iterate from i = 5 to i = 15:

   • For i = 5, box number = 5, count[5] += 1
   • For i = 6, box number = 6, count[6] += 1
   • For i = 7, box number = 7, count[7] += 1
   • For i = 8, box number = 8, count[8] += 1
   • For i = 9, box number = 9, count[9] += 1
   • For i = 10, box number = 1, count[1] += 1
   • For i = 11, box number = 2, count[2] += 1
   • For i = 12, box number = 3, count[3] += 1
   • For i = 13, box number = 4, count[4] += 1
   • For i = 14, box number = 5, count[5] += 1
   • For i = 15, box number = 6, count[6] += 1

3. Find the maximum count in the count array:

   • max_count = 2 (box 5 and box 6 have the most balls with 2 balls each)

The output should be 2.

Python Solution

1class Solution:
2    def countBalls(self, lowLimit: int, highLimit: int) -> int:
3        def sum_of_digits(num: int) -> int:
4            s = 0
5            while num > 0:
6                s += num % 10
7                num //= 10
8            return s
9        
10        count = [0] * 46
11        
12        for i in range(lowLimit, highLimit + 1):
13            box_number = sum_of_digits(i)
14            count[box_number] += 1
15        
16        return max(count)

Java Solution

1class Solution {
2    public int countBalls(int lowLimit, int highLimit) {
3        int[] count = new int[46];
4        
5        for (int i = lowLimit; i <= highLimit; i++) {
6            int boxNumber = sumOfDigits(i);
7            count[boxNumber]++;
8        }
9        
10        int maxCount = 0;
11        for (int cnt : count) {
12            maxCount = Math.max(maxCount, cnt);
13        }
14        
15        return maxCount;
16    }
17    
18    private int sumOfDigits(int num) {
19        int sum = 0;
20        while (num > 0) {
21            sum += num % 10;
22            num /= 10;
23        }
24        return sum;
25    }
26}

JavaScript Solution

1class Solution {
2    countBalls(lowLimit, highLimit) {
3        const count = new Array(46).fill(0);
4        
5        for (let i = lowLimit; i <= highLimit; i++) {
6            const boxNumber = this.sumOfDigits(i);
7            count[boxNumber]++;
8        }
9        
10        return Math.max(...count);
11    }
12    
13    sumOfDigits(num) {
14        let sum = 0;
15        while (num > 0) {
16            sum += num % 10;
17            num = Math.floor(num / 10);
18        }
19        return sum;
20    }
21}

C++ Solution

1class Solution {
2public:
3    int countBalls(int lowLimit, int highLimit) {
4        vector<int> count(46, 0);
5        
6        for (int i = lowLimit; i <= highLimit; ++i) {
7            int boxNumber = sumOfDigits(i);
8            count[boxNumber]++;
9        }
10        
11        return *max_element(count.begin(), count.end());
12    }
13    
14    int sumOfDigits(int num) {
15        int sum = 0;
16        while (num > 0) {
17            sum += num % 10;
18            num /= 10;
19        }
20        return sum;
21    }
22};

C# Solution

1public class Solution {
2    public int CountBalls(int lowLimit, int highLimit) {
3        int[] count = new int[46];
4        
5        for (int i = lowLimit; i <= highLimit; i++) {
6            int boxNumber = SumOfDigits(i);
7            count[boxNumber]++;
8        }
9        
10        int maxCount = 0;
11        foreach (int cnt in count) {
12            maxCount = Math.Max(maxCount, cnt);
13        }
14        
15        return maxCount;
16    }
17    
18    private int SumOfDigits(int num) {
19        int sum = 0;
20        while (num > 0) {
21            sum += num % 10;
22            num /= 10;
23        }
24        return sum;
25    }
26}

Time and Space Complexity

All the solutions have a time complexity of O(max(n, 46)), where n is the number of balls (highLimit - lowLimit + 1). The time complexity is determined based on the iteration through the range of balls and then the maximum count of balls in the boxes.

The space complexity is O(46), as an array of size 46 is used to store the count of balls in the boxes.

These complexities are the same for the solutions in all five languages (Python, Java, JavaScript, C++, and C#).