Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1742.html

1742. Maximum Number of Balls in a Box

Level

Easy

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 <= 10^5

Solution

Since highLimit <= 10^5, the sum of digits of each number is at most 46. Create an array sums where sums[i] is the number of balls that have sum of digits equal to i. Loop over all numbers from lowLimit to highLimit. For each number, calculate the sum of digits and update the array. Finally, loop over the array and obtain the maximum count.

• Java
• Python
• C++
• Go
• TypeScript

• class Solution {
      public int countBalls(int lowLimit, int highLimit) {
          int[] sums = new int[50];
          for (int i = lowLimit; i <= highLimit; i++) {
              int sum = getSumOfDigits(i);
              sums[sum]++;
          }
          int maxCount = 0;
          for (int i = 0; i < 50; i++)
              maxCount = Math.max(maxCount, sums[i]);
          return maxCount;
      }
  
      public int getSumOfDigits(int num) {
          int sum = 0;
          while (num > 0) {
              sum += num % 10;
              num /= 10;
          }
          return sum;
      }
  }
  
  ############
  
  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();
      }
  }
  

• 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)
  
  ############
  
  # 1742. Maximum Number of Balls in a Box
  # https://leetcode.com/problems/maximum-number-of-balls-in-a-box
  
  class Solution:
      def countBalls(self, lowLimit: int, highLimit: int) -> int:
          mp = collections.defaultdict(int)
          
          for i in range(lowLimit, highLimit+1):
              value = 0
              
              while i >= 1:
                  value += i%10
                  i //= 10
                  
              mp[value] += 1
  
          return max(mp.values())
  
  

• 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;
      }
  };
  

• 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
  }
  

• 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);
  }
  
  

All Problems

All Solutions