describe

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.	
Copy the code

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.
Copy the code

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.
Copy the code

Note:

1 <= lowLimit <= highLimit <= 10^5
Copy the code

parsing

The number of balls is stored in the dictionary balls. The sum of each digit of item is the key, and the number of balls that can be stored is the value. Get the result for each key at the end of the loop, and then find the maximum value.

answer

class Solution(object):
    def countBalls(self, lowLimit, highLimit):
        """
        :type lowLimit: int
        :type highLimit: int
        :rtype: int
        """
        balls = {}
        def sum(num):
            result = 0
            while num>0:
                result += num%10
                num=num//10
            return result
        for item in range(lowLimit,highLimit+1):
            tmp = sum(item)
            if tmp not in balls:
                balls[tmp]=1
            else:
                balls[tmp]+=1
        return max(balls.values())
        	      
		
Copy the code

The results

Given the submission in the Python online submissions in each node. Memory Usage: 10000 ms Each node has 15.9 MB in the linked list, less than 86.84% of Python online submissions for Maximum Number of Balls in a Box.Copy the code

Original link: leetcode.com/problems/ma…

Your support is my biggest motivation