This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

You work in a toy factory that produces small balls, with n balls numbered from lowLimit to highLimit (including lowLimit and highLimit, i.e. N == highLimit -lowlimit + 1). There are also an unlimited number of boxes, numbered from 1 to infinity.

Your job is to place each ball in a box whose number should be equal to the sum of each number on the ball. For example, ball # 321 would go into box # 3 + 2 + 1 = 6, and ball # 10 would go into box # 1 + 0 = 1.

Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls. If more than one box satisfies the requirement of having the most balls, simply return the number of balls in any one of the boxes.

Example 1: Input: lowLimit = 1, highLimit = 10 Output: 2 Description: Box number: 1 2 3 4 5 6 7 8 9 10 11... Number of balls: 2 1 1 1 1 1 1 0 0... Box 1 has the most balls, and the number of balls is 2. 1 <= lowLimit <= highLimit <= 105 https://leetcode-cn.com/problems/maximum-number-of-balls-in-a-box copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • This topic is a long one, so we should be patient in analyzing it. Analyze the question carefully and understand the meaning of the question. The question is:

Sum the numbers of the balls, and the subscripts of the boxes.

According to the passage,

The number range of the ball

  • 1 <= lowLimit <= highLimit <= 10 ^ 5

  • Therefore, the ball number is at least 1 and at most 100000.

  • The sum of box numbers ranges from 1 to 45(calculated from ball number 99999). So: Apply for a box array of length 46 to hold the balls.

AC code

class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        int ans = 0;
        int[] box = new int[46];
        for (int i = lowLimit; i <= highLimit; i++) {
            int ballNumber = getSum(i);
            box[ballNumber]++;
            ans = Math.max(ans, box[ballNumber]);
        }
        return ans;
    }

    private int getSum(int num) {
        int sum = 0;
        while (num >= 10) {
            sum += num % 10;
            num /= 10;
        }
        sum += num;
        returnsum; }}Copy the code

Submit tests:

AC smoothly!

conclusion

  • The above code has time complexity O(n * n) and space complexity O(1).
  • When the topic is long, we should also carefully analyze the thinking, do not be impatient, one step at a time!
  • Stick to the daily question, come on!