# Count Largest Group
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-largest-group)
Canonical: https://scaleengineer.com/dsa/problems/count-largest-group
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Hash Table
**Companies:** [Mercari](https://scaleengineer.com/companies/mercari)
---
## Problem
You are given an integer `n`.

We need to group the numbers from `1` to `n` according to the sum of its digits. For example, the numbers 14 and 5 belong to the **same** group, whereas 13 and 3 belong to **different** groups.

Return the number of groups that have the largest size, i.e. the **maximum** number of elements.

**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`

# Approaches
## Brute-Force with Direct Digit Sum Calculation
This approach directly simulates the process described in the problem. It iterates through each number from 1 to `n`, and for each number, it calculates the sum of its digits. These sums are used to group the numbers. A frequency array tracks the size of each group. After populating the frequencies, a final pass is made to find the largest group size and count how many groups have this size.
**Time:** O(n log n). The outer loop runs `n` times. For each number `i`, calculating the sum of its digits takes `O(log10(i))` time. Thus, the total time complexity is dominated by this calculation for all numbers up to `n`. · **Space:** O(1), as we use a fixed-size array of size 37 to store the group counts. The space required does not scale with the input `n`.
**Pros:** The logic is straightforward and easy to understand.; It uses constant extra space, as the size of the frequency array is fixed and does not depend on `n`.
**Cons:** The time complexity is not optimal because calculating the digit sum for each number involves a loop, leading to an overall `O(n log n)` complexity.
### Explanation
The core of this method is a loop that runs from 1 to `n`. Inside this loop, we compute the sum of digits for the current number. A helper function, say `getDigitSum(num)`, can be implemented for this. This function would initialize a `sum` variable to zero, and then in a `while` loop, it would continuously add `num % 10` to the `sum` and update `num` to `num / 10` until `num` becomes zero. The maximum possible sum of digits for a number up to `10^4` is for 9999, which is 36. Therefore, an array of size 37 is sufficient to act as a frequency map, where the index represents the digit sum and the value at that index represents the size of the group.

After calculating the digit sum for a number `i`, we increment the count at the corresponding index in our frequency array. While doing this, we can also keep track of the maximum frequency seen so far. After the main loop finishes, we iterate through the frequency array one more time to count how many entries match the maximum frequency found. This count is the result.

```java
class Solution {
    private int getDigitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public int countLargestGroup(int n) {
        // Max sum for n=10000 is for 9999 -> 36. Array size 37 is safe.
        int[] counts = new int[37];
        int maxSize = 0;

        for (int i = 1; i <= n; i++) {
            int sum = getDigitSum(i);
            counts[sum]++;
            if (counts[sum] > maxSize) {
                maxSize = counts[sum];
            }
        }

        int result = 0;
        for (int count : counts) {
            if (count == maxSize) {
                result++;
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize a frequency map (or an array since digit sums are small) to store the size of each group. For instance, an integer array `counts` of size 37 (for sums 1 to 36) initialized to zeros.
*   Loop through each number `i` from 1 to `n`.
*   For each number `i`, create a helper function `getDigitSum(i)` that calculates the sum of its digits. This function works by repeatedly taking the number modulo 10 to get the last digit and dividing the number by 10 to remove the last digit, until the number becomes 0.
*   Use the returned digit sum as an index into the `counts` array and increment the value: `counts[digitSum]++`.
*   After iterating through all numbers, scan the `counts` array to find the maximum group size, `maxSize`.
*   Scan the `counts` array again to count how many groups have a size equal to `maxSize`.
*   Return this final count.

## Dynamic Programming Approach
This approach uses dynamic programming to optimize the calculation of the digit sums. It's based on the observation that the sum of digits of a number `i` can be easily computed if we know the sum of digits of `i / 10`. By storing the computed sums in an array, we can calculate the sum for each number in constant time, leading to an overall linear time solution.
**Time:** O(n). The main loop runs `n` times, and all operations inside the loop (array access, addition, modulo) are constant time operations. · **Space:** O(n), due to the extra `digitSum` array of size `n + 1` used to store intermediate results for the dynamic programming approach.
**Pros:** More efficient time-wise than the brute-force approach, with a linear time complexity.; The logic for calculating digit sums is clean and based on a simple recurrence.
**Cons:** Requires `O(n)` extra space for the dynamic programming array, which is less space-efficient than the brute-force approach.
### Explanation
We can define `dp[i]` as the sum of digits of number `i`. There's a simple recurrence relation: `dp[i] = dp[i / 10] + (i % 10)`. For example, the sum of digits for 123 is `(sum of digits for 12) + 3`. We can use an array, let's call it `digitSum`, of size `n + 1` to store these values.

We iterate from `i = 1` to `n`. In each step, we compute `digitSum[i]` using our recurrence. Since `i / 10` is always less than `i`, `digitSum[i / 10]` will have already been computed. Once we have the digit sum for `i`, we use it to update our group size frequency array, `counts`. We also track the maximum group size (`maxSize`) as we populate the `counts` array.

After the loop finishes, we have the final `maxSize`. A simple iteration over the `counts` array will give us the number of groups that have this size. This approach trades `O(n)` space to reduce the time complexity from `O(n log n)` to `O(n)`.

```java
class Solution {
    public int countLargestGroup(int n) {
        // Max sum for n=10000 is for 9999 -> 36.
        int[] counts = new int[37];
        int[] digitSum = new int[n + 1];
        int maxSize = 0;
        
        for (int i = 1; i <= n; i++) {
            // DP relation: sum(i) = sum(i/10) + i%10
            digitSum[i] = digitSum[i / 10] + (i % 10);
            counts[digitSum[i]]++;
            maxSize = Math.max(maxSize, counts[digitSum[i]]);
        }

        int result = 0;
        for (int count : counts) {
            if (count == maxSize) {
                result++;
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an integer array `digitSum` of size `n + 1` to store the sum of digits for each number from 0 to `n`.
*   Initialize an integer array `counts` of size 37 to store the frequency of each digit sum.
*   Initialize a variable `maxSize = 0` to keep track of the largest group size.
*   Loop through each integer `i` from 1 to `n`.
*   Inside the loop, calculate `digitSum[i]` using the dynamic programming relation: `digitSum[i] = digitSum[i / 10] + (i % 10)`.
*   Increment the count for this sum in the `counts` array: `counts[digitSum[i]]++`.
*   Update `maxSize = Math.max(maxSize, counts[digitSum[i]])`.
*   After the loop, initialize `result = 0`.
*   Iterate through the `counts` array. If a count is equal to `maxSize`, increment `result`.
*   Return `result`.

# Solutions
### Java

```java
class Solution {
public
  int countLargestGroup(int n) {
    int[] cnt = new int[40];
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; ++i) {
      int s = 0;
      for (int x = i; x > 0; x /= 10) {
        s += x % 10;
      }
      ++cnt[s];
      if (mx < cnt[s]) {
        mx = cnt[s];
        ans = 1;
      } else if (mx == cnt[s]) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int countLargestGroup ( int n ) { int cnt [ 40 ]{}; int ans = 0 , mx = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int s = 0 ; for ( int x = i ; x ; x /= 10 ) { s += x % 10 ; } ++ cnt [ s ]; if ( mx < cnt [ s ]) { mx = cnt [ s ]; ans = 1 ; } else if ( mx == cnt [ s ]) { ++ ans ; } } return ans ; } };
```

### Python

```python
class Solution : def countLargestGroup ( self , n : int ) -> int : cnt = Counter () ans = mx = 0 for i in range ( 1 , n + 1 ): s = 0 while i : s += i % 10 i //= 10 cnt [ s ] += 1 if mx < cnt [ s ]: mx = cnt [ s ] ans = 1 elif mx == cnt [ s ]: ans += 1 return ans
```