LeetCode 1742. Maximum Number of Balls in a Box Solution in Java, C++, Python & More | Explanation + Code

Description

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 <= 105

Solutions

Solution 1: Array + Simulation

Observing the problem's data range, the maximum number of balls does not exceed 10⁵, so the maximum sum of the digits of each number is less than 50. Therefore, we can directly create an array cnt of length 50 to count the number of occurrences of each digit sum.

The answer is the maximum value in the array cnt.

The time complexity is O(n × log_{10}m). Here, n = highLimit - lowLimit + 1, and m = highLimit.

PythonJavaC++GoTypeScriptRustJavaScriptC#

class Solution: def countBalls(self, lowLimit: int, highLimit: int) -> int: cnt = [0] * 50 for x in range(lowLimit, highLimit + 1): y = 0 while x: y += x % 10 x //= 10 cnt[y] += 1 return max(cnt)(code-box)

class Solution { public int countBalls(int lowLimit, int highLimit) { int[] cnt = new int[50]; for (int i = lowLimit; i <= highLimit; ++i) { int y = 0; for (int x = i; x > 0; x /= 10) { y += x % 10; } ++cnt[y]; } return Arrays.stream(cnt).max().getAsInt(); } }(code-box)

class Solution { public: int countBalls(int lowLimit, int highLimit) { int cnt[50] = {0}; int ans = 0; for (int i = lowLimit; i <= highLimit; ++i) { int y = 0; for (int x = i; x; x /= 10) { y += x % 10; } ans = max(ans, ++cnt[y]); } return ans; } };(code-box)

func countBalls(lowLimit int, highLimit int) (ans int) { cnt := [50]int{} for i := lowLimit; i <= highLimit; i++ { y := 0 for x := i; x > 0; x /= 10 { y += x % 10 } cnt[y]++ if ans < cnt[y] { ans = cnt[y] } } return }(code-box)

function countBalls(lowLimit: number, highLimit: number): number { const cnt: number[] = Array(50).fill(0); for (let i = lowLimit; i <= highLimit; ++i) { let y = 0; for (let x = i; x; x = Math.floor(x / 10)) { y += x % 10; } ++cnt[y]; } return Math.max(...cnt); }(code-box)

impl Solution { pub fn count_balls(low_limit: i32, high_limit: i32) -> i32 { let mut cnt = vec![0; 50]; for x in low_limit..=high_limit { let mut y = 0; let mut n = x; while n > 0 { y += n % 10; n /= 10; } cnt[y as usize] += 1; } *cnt.iter().max().unwrap() } }(code-box)

/** * @param {number} lowLimit * @param {number} highLimit * @return {number} */ var countBalls = function (lowLimit, highLimit) { const cnt = Array(50).fill(0); for (let i = lowLimit; i <= highLimit; ++i) { let y = 0; for (let x = i; x; x = Math.floor(x / 10)) { y += x % 10; } ++cnt[y]; } return Math.max(...cnt); };(code-box)

public class Solution { public int CountBalls(int lowLimit, int highLimit) { int[] cnt = new int[50]; for (int x = lowLimit; x <= highLimit; x++) { int y = 0; int n = x; while (n > 0) { y += n % 10; n /= 10; } cnt[y]++; } return cnt.Max(); } }(code-box)