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 1 to n. Each ball is sent to a box with a number equal to the sum of digits of the ball’s number. For example, ball number 321 will be sent to box 3 + 2 + 1 = 6 and ball number 10 will be sent to box 1 + 0 = 1. Given two numbers lowLimit and highLimit, return the number of balls in the box with the most balls.

Clarifying Questions

  1. What is the range of lowLimit and highLimit?
    • 1 <= lowLimit <= highLimit <= 10^5
  2. What is the maximum value for the sum of digits of the ball numbers?
    • Since the highest value for a ball is 10^5, the highest sum of digits is 9 + 9 + 9 + 9 + 9 = 45.
  3. Are the lowLimit and highLimit inclusive?
    • Yes, both lowLimit and highLimit are inclusive ranges.

Strategy

  1. Sum of Digits Calculation:
    • For each ball number i in the range [lowLimit, highLimit], calculate the sum of its digits.
  2. HashMap for Counting:
    • We will use an unordered_map to count the number of balls in each possible box.
  3. Finding the Maximum:
    • Iterate through the map to find the maximum count of balls in any box.

Code

#include <iostream>
#include <unordered_map>
using namespace std;

int getSumOfDigits(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int countBalls(int lowLimit, int highLimit) {
    unordered_map<int, int> boxCount;
    int maxBalls = 0;
    
    for (int i = lowLimit; i <= highLimit; ++i) {
        int boxNumber = getSumOfDigits(i);
        boxCount[boxNumber]++;
        maxBalls = max(maxBalls, boxCount[boxNumber]);
    }
    
    return maxBalls;
}

int main() {
    int lowLimit = 1, highLimit = 10;
    cout << countBalls(lowLimit, highLimit) << endl;  // Output should be 2
    
    return 0;
}

Time Complexity

Thus, the overall time complexity is dominated by the iteration and sum of digits calculation, making it O(n * log N) where n is the range size and log N is the max digit sum calculation.

In the given constraints, this approach will be efficient and work within acceptable limits.

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