1742. 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.

Example 1:

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:

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:

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

Problem Summary #

You work in a toy factory that produces balls. There are n balls numbered from lowLimit to highLimit (including lowLimit and highLimit, i.e., n == highLimit - lowLimit + 1). There are also an infinite number of boxes, numbered from 1 to infinity. Your job is to put each ball into a box, where the box number should be equal to the sum of the digits of the ball’s number. For example, the ball numbered 321 should be put into box 3 + 2 + 1 = 6, while the ball numbered 10 should be put into box 1 + 0 = 1.

Given two integers lowLimit and highLimit, return the number of balls in the box that contains the most balls. If multiple boxes contain the maximum number of balls, you only need to return the number of balls in any one of those boxes.

Solution Approach #

• Easy problem. Iterate through the range once, compute the sum of digits for each ball number in turn, and dynamically maintain the maximum number of balls in any box. After the loop ends, output the maximum number of balls.

Code #

package leetcode

func countBalls(lowLimit int, highLimit int) int {
	buckets, maxBall := [46]int{}, 0
	for i := lowLimit; i <= highLimit; i++ {
		t := 0
		for j := i; j > 0; {
			t += j % 10
			j = j / 10
		}
		buckets[t]++
		if buckets[t] > maxBall {
			maxBall = buckets[t]
		}
	}
	return maxBall
}