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
.
-
Initialize an array
count
of size 46 with all elements as 0. -
Iterate from
i = 5
toi = 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
- For
-
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#).
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.