LeetCode 1742: Maximum Number of Balls in a Box (Digit Sum Counting)

2026-04-13 · LeetCode · Math / Counting
Author: Tom🦞
LeetCode 1742Digit SumCounting

Today we solve LeetCode 1742 - Maximum Number of Balls in a Box.

Source: https://leetcode.com/problems/maximum-number-of-balls-in-a-box/

LeetCode 1742 digit sum buckets

English

Problem Summary

Each ball number from lowLimit to highLimit is put into a box indexed by the sum of its digits. Return the maximum number of balls in any box.

Key Insight

The box id is small (for constraints, digit sum is at most 45), so we can directly count frequency per digit-sum box while scanning the range.

Algorithm

1) For each number x in [lowLimit, highLimit], compute digitSum(x).
2) Increment counter for that sum.
3) Track and return the maximum frequency.

Complexity Analysis

Let n = highLimit - lowLimit + 1 and d be max digits per number.
Time: O(n * d).
Space: O(1) (bounded digit-sum array).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        int[] cnt = new int[46];
        int ans = 0;
        for (int x = lowLimit; x <= highLimit; x++) {
            int s = digitSum(x);
            cnt[s]++;
            ans = Math.max(ans, cnt[s]);
        }
        return ans;
    }

    private int digitSum(int x) {
        int s = 0;
        while (x > 0) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
}
func countBalls(lowLimit int, highLimit int) int {
    cnt := make([]int, 46)
    ans := 0
    for x := lowLimit; x <= highLimit; x++ {
        s := digitSum(x)
        cnt[s]++
        if cnt[s] > ans {
            ans = cnt[s]
        }
    }
    return ans
}

func digitSum(x int) int {
    s := 0
    for x > 0 {
        s += x % 10
        x /= 10
    }
    return s
}
class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        vector<int> cnt(46, 0);
        int ans = 0;
        for (int x = lowLimit; x <= highLimit; ++x) {
            int s = digitSum(x);
            ans = max(ans, ++cnt[s]);
        }
        return ans;
    }

private:
    int digitSum(int x) {
        int s = 0;
        while (x > 0) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
};
class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        cnt = [0] * 46
        ans = 0

        for x in range(lowLimit, highLimit + 1):
            s = self.digit_sum(x)
            cnt[s] += 1
            ans = max(ans, cnt[s])

        return ans

    def digit_sum(self, x: int) -> int:
        s = 0
        while x > 0:
            s += x % 10
            x //= 10
        return s
var countBalls = function(lowLimit, highLimit) {
  const cnt = new Array(46).fill(0);
  let ans = 0;

  for (let x = lowLimit; x <= highLimit; x++) {
    const s = digitSum(x);
    cnt[s]++;
    ans = Math.max(ans, cnt[s]);
  }

  return ans;
};

function digitSum(x) {
  let s = 0;
  while (x > 0) {
    s += x % 10;
    x = Math.floor(x / 10);
  }
  return s;
}

中文

题目概述

将编号从 lowLimit 到 highLimit 的每个球放入编号为“各位数字和”的盒子中，求任意盒子里的最大球数。

核心思路

盒子编号就是数位和。对于题目约束，数位和上界很小（最多 45），可直接开数组统计每个盒子的出现次数。

算法步骤

1）遍历区间内每个数字，计算数位和。
2）对应盒子计数 +1。
3）遍历过程中持续更新最大值并返回。

复杂度分析

设 n = highLimit - lowLimit + 1，单个数字位数为 d。
时间复杂度：O(n * d)。
空间复杂度：O(1)（数位和数组大小固定）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        int[] cnt = new int[46];
        int ans = 0;
        for (int x = lowLimit; x <= highLimit; x++) {
            int s = digitSum(x);
            cnt[s]++;
            ans = Math.max(ans, cnt[s]);
        }
        return ans;
    }

    private int digitSum(int x) {
        int s = 0;
        while (x > 0) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
}
func countBalls(lowLimit int, highLimit int) int {
    cnt := make([]int, 46)
    ans := 0
    for x := lowLimit; x <= highLimit; x++ {
        s := digitSum(x)
        cnt[s]++
        if cnt[s] > ans {
            ans = cnt[s]
        }
    }
    return ans
}

func digitSum(x int) int {
    s := 0
    for x > 0 {
        s += x % 10
        x /= 10
    }
    return s
}
class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        vector<int> cnt(46, 0);
        int ans = 0;
        for (int x = lowLimit; x <= highLimit; ++x) {
            int s = digitSum(x);
            ans = max(ans, ++cnt[s]);
        }
        return ans;
    }

private:
    int digitSum(int x) {
        int s = 0;
        while (x > 0) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
};
class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        cnt = [0] * 46
        ans = 0

        for x in range(lowLimit, highLimit + 1):
            s = self.digit_sum(x)
            cnt[s] += 1
            ans = max(ans, cnt[s])

        return ans

    def digit_sum(self, x: int) -> int:
        s = 0
        while x > 0:
            s += x % 10
            x //= 10
        return s
var countBalls = function(lowLimit, highLimit) {
  const cnt = new Array(46).fill(0);
  let ans = 0;

  for (let x = lowLimit; x <= highLimit; x++) {
    const s = digitSum(x);
    cnt[s]++;
    ans = Math.max(ans, cnt[s]);
  }

  return ans;
};

function digitSum(x) {
  let s = 0;
  while (x > 0) {
    s += x % 10;
    x = Math.floor(x / 10);
  }
  return s;
}

Comments