algoadvance

Leetcode 1742. Maximum Number of Balls in a Box

Problem Statement:

You are working in a ball factory where you have n balls numbered from lowLimit to highLimit inclusive. You want to distribute the balls into m boxes. To do this, you can use a hashing function defined as the summation of the digits of the ball number. The box number that a ball goes into is the result of the hashing function modulo m.

Find the box that has the maximum number of balls. If there are multiple such boxes, return any of them.

Clarifying Questions:

1. Range of Numbers:
   • What are the constraints on lowLimit, highLimit, and m?
2. Function Definition:
   • Should the hashing function handle negative numbers, or is it guaranteed that ball numbers are positive?

Strategy:

1. Digit Sum Function:
   • Implement a helper function to compute the sum of the digits of a given number.
2. Distribution and Counting:
   • Iterate over each number from lowLimit to highLimit.
   • Use the digit sum function to determine the box number for each ball by calculating digit_sum % m.
   • Use a hash map to count the number of balls in each box.
3. Finding the Maximum:
   • Traverse the hash map to find the box with the maximum number of balls.

Time Complexity:

• The time complexity is dominated by the need to process each ball number from lowLimit to highLimit. Each computation involves summing the digits (which is a logarithmic operation relative to the number).

Let’s assume the average digit sum operation takes constant time: O(log n) ~ O(1), then:

• Overall time complexity is O(highLimit - lowLimit + 1), i.e., linear in the number of balls.

Implementation in Java:

import java.util.HashMap;
import java.util.Map;

public class MaximumNumberOfBallsInBox {
    
    public static void main(String[] args) {
        int lowLimit = 1;
        int highLimit = 10;
        int m = 5;
        
        System.out.println(maximumBallsInBox(lowLimit, highLimit, m));
    }

    public static int maximumBallsInBox(int lowLimit, int highLimit, int m) {
        // Map to store counts of balls in each box
        Map<Integer, Integer> boxCountMap = new HashMap<>();
        
        // Iterate from lowLimit to highLimit
        for (int i = lowLimit; i <= highLimit; i++) {
            int boxNumber = digitSum(i) % m;
            boxCountMap.put(boxNumber, boxCountMap.getOrDefault(boxNumber, 0) + 1);
        }
        
        // Find the box with maximum balls
        int maxBalls = 0;
        for (int count : boxCountMap.values()) {
            if (count > maxBalls) {
                maxBalls = count;
            }
        }
        
        // If there are multiple such boxes, any will do - return maxBalls
        return maxBalls;
    }

    // Helper method to calculate sum of digits
    private static int digitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

Explanation:

• digitSum Function: Computes the sum of the digits for the ball number.
• maximumBallsInBox Method: Iterates over the ball numbers, computes their box using the digit sum modulo m, and maintains a count of balls per box in a hash map.
• Finally, it finds the maximum count of balls in any box and returns it.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?