We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Balls in a Box

Difficulty: Easy

Problem Description

You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive. Your job is to put each ball in the box with a number equal to the sum of digits of the ball's number. Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.

Key Insights

  • Each ball's box number is determined by the sum of its digits.
  • The range of ball numbers is defined by lowLimit to highLimit.
  • We can use a counting approach to keep track of how many balls are in each box.
  • The maximum number of balls in any box can be found by iterating through each ball number and calculating its box number.

Space and Time Complexity

Time Complexity: O(n * d), where n is the number of balls and d is the maximum number of digits in a number in the range. Space Complexity: O(k), where k is the number of unique box numbers (bounded by the maximum possible sum of digits).

Solution

To solve this problem, we can use a hash table (or a dictionary) to count the number of balls in each box. We will iterate through each number from lowLimit to highLimit, compute the sum of its digits, and use this sum as a key in our hash table to keep track of the count of balls in each corresponding box. Finally, we will return the maximum value from our hash table, which represents the box with the most balls.

Code Solutions

def sum_of_digits(num):
    return sum(int(digit) for digit in str(num))

def count_balls(lowLimit, highLimit):
    box_count = {}
    for ball in range(lowLimit, highLimit + 1):
        box_number = sum_of_digits(ball)
        if box_number in box_count:
            box_count[box_number] += 1
        else:
            box_count[box_number] = 1
    return max(box_count.values())

# Example usage:
print(count_balls(1, 10))  # Output: 2
← Back to All Questions