Count Largest Group

Leetcode Problem:

• Count Largest Group

Summary

• Find the number of groups that have the largest size where each number from 1 to n is grouped according to the sum of its digits.

Approach

• The approach used is to calculate the sum of digits for each number from 1 to n, group the numbers by the sum of their digits, and then count the number of groups with the largest size.

Complexity

• O(n log n) due to the calculation of sum of digits for each number, where n is the input number.

Explanation

• The solution code first defines a helper function to calculate the sum of digits for a given number
• Then, it initializes an array to store the groups of numbers with the same sum of digits
• It iterates through each number from 1 to n, calculates the sum of its digits, and adds it to the corresponding group in the array
• If the size of the current group is larger than the largest group size found so far, it updates the largest group size and sets the answer to 1
• If the size of the current group is equal to the largest group size, it increments the answer
• Finally, it returns the answer, which represents the number of groups with the largest size.

Solution Code:

class Solution {
public:
    int getSum(int n){
        int s = 0;
        while(n){
            s += n % 10;
            n /= 10;
        }
        return s;
    }
    int countLargestGroup(int n) {
        vector groups[37];
        int largestGroupSize = 0;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int group = getSum(i);
            groups[group].push_back(i);
            if(largestGroupSize < groups[group].size()){
                largestGroupSize = groups[group].size();
                ans = 1;
            } else if(largestGroupSize == groups[group].size()){
                ans++;
            }
        }
        return ans;
    }
};