1399. Count Largest Group

[mah-shamim]

Topics: Hash Table, Math

You are given an integer n.

Each number from 1 to n is grouped according to the sum of its digits.

Return the number of groups that have the largest size.

Example 1:

• Input: n = 13
• Output: 4
• Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
  [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9].
  There are 4 groups with largest size.

Example 2:

• Input: n = 2
• Output: 2
• Explanation: There are 2 groups [1], [2] of size 1.

Constraints:

• 1 <= n <= 104

Hint:

1. Count the digit sum for each integer in the range and find out the largest groups.

[mah-shamim]

We need to group numbers from 1 to n based on the sum of their digits and determine how many groups have the largest size.

Approach

1. Calculate Digit Sums: For each number from 1 to n, compute the sum of its digits.
2. Track Group Sizes: Use a hash map (associative array in PHP) to count how many numbers fall into each digit sum group.
3. Determine Largest Group: Find the maximum size among all groups.
4. Count Largest Groups: Count how many groups have this maximum size.

Let's implement this solution in PHP: 1399. Count Largest Group

<?php
/**
 * @param Integer $n
 * @return Integer
 */
function countLargestGroup($n) {
    $counts = array();
    for ($i = 1; $i <= $n; $i++) {
        $s = digitSum($i);
        if (isset($counts[$s])) {
            $counts[$s]++;
        } else {
            $counts[$s] = 1;
        }
    }
    $max = max($counts);
    $result = 0;
    foreach ($counts as $cnt) {
        if ($cnt == $max) {
            $result++;
        }
    }
    return $result;
}

/**
 * @param $num
 * @return int
 */
function digitSum($num) {
    $sum = 0;
    while ($num != 0) {
        $sum += $num % 10;
        $num = (int) ($num / 10);
    }
    return $sum;
}

// Example usage:
echo countLargestGroup(13); // Output: 4
echo countLargestGroup(2); // Output: 2
?>

Explanation:

1. Digit Sum Calculation: The digitSum function computes the sum of digits of a number by repeatedly extracting the last digit using modulo 10 and then removing the last digit by integer division by 10.
2. Group Counting: As we iterate through each number from 1 to n, we use an associative array $counts to keep track of how many numbers correspond to each digit sum.
3. Finding Maximum Group Size: The max function is used to find the largest group size from the associative array.
4. Counting Largest Groups: We iterate through the counts to determine how many groups have the maximum size, which is our result.

This approach efficiently groups numbers by their digit sums and then processes these groups to find the required result, ensuring optimal performance even for the upper constraint of n = 10,000.

[topugit]

Thanks for solving the problem of "Count Largest Group"

[mah-shamim]

Thanks