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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Balls in a Box

Number: 1844

Difficulty: Easy

Paid? No

Companies: AppDynamics, Lucid

Problem Description

You are given an inclusive range of ball numbers from lowLimit to highLimit. Each ball is placed into a box corresponding to the sum of its digits. The goal is to determine the maximum number of balls found in any single box.

Key Insights

  • Compute the sum of digits for each ball number to determine its corresponding box.
  • Use a hash table (or dictionary) to count how many balls fall into each box.
  • The number of iterations is linear with respect to the number of balls, and the digit sum operation is efficient due to the limited number of digits.
  • The maximum possible digit sum is small compared to the number of balls; this means the space is effectively constant.

Space and Time Complexity

Time Complexity: O(n * d) where n is the number of balls and d is the number of digits per ball (d is small). Space Complexity: O(1) since the number of possible digit sum values is bounded by a constant (the maximum digit sum for highLimit).

Solution

The solution iterates from lowLimit to highLimit, calculates the digit sum for each ball to determine the corresponding box number, and uses a dictionary (or similar data structure) to keep track of the ball counts for each box. Finally, the maximum count from the dictionary is returned. This approach leverages a simple traversal and counting mechanism to efficiently solve the problem.

Code Solutions

# Python solution for Maximum Number of Balls in a Box

def countBalls(lowLimit, highLimit):
    # Function to calculate the sum of digits of a number.
    def digit_sum(num):
        total = 0
        while num:
            total += num % 10  # Add the last digit
            num //= 10       # Remove the last digit
        return total

    # Dictionary to store the count of balls in each box.
    box_counts = {}
    
    # Iterate from lowLimit to highLimit (inclusive).
    for ball in range(lowLimit, highLimit + 1):
        # Determine the box number by computing the digit sum.
        box_num = digit_sum(ball)
        # Increment count using dictionary's get method with a default value.
        box_counts[box_num] = box_counts.get(box_num, 0) + 1

    # Return the maximum count among all boxes.
    return max(box_counts.values())

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