1399. Count Largest Group

UnknownView on LeetCode

Hash Table Math Counting

Time: O(n log n)

Space: O(1)

Problem Overview

For each integer from 1 to n, compute the sum of its decimal digits.

Intuition

For each integer from 1 to n, compute the sum of its decimal digits. Group numbers by digit sum and count group sizes. The answer is how many integers share the most common digit sum (largest group).

Algorithm

1Create frequency map digitSum -> count, size at most 46 for n <= 10^4.
2For num from 1 to n: compute digit sum by repeated mod/div by 10.
3Increment freq[digitSum].
4Track max frequency while iterating (or scan map at end).
5Return the maximum frequency value.

Example Walkthrough

Input: n = 13

1.Digit sums: 1..9 -> sum equals self; 10->1, 11->2, 12->3, 13->4.
2.Largest group size is 2 (several sums tie at 2).

Output: 2

Common Pitfalls

•Return count of members in largest group, not the digit sum itself.
•Ties for max group size still return that shared count.
•Brute force over 1..n is fine for n <= 10^4.

1399.cs

// Approach: Count numbers per digit-sum group (max sum = 36 for 4-digit); return count of groups with maximum size.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int CountLargestGroup(int n)
    {
        int[] count = new int[9 * 4 + 1];
        for (int i = 1; i <= n; ++i)
            ++count[GetDigitSum(i)];
        int mx = count.Max();
        return count.Count(c => c == mx);
    }

    private int GetDigitSum(int num)
    {
        int digitSum = 0;
        while (num > 0)
        {
            digitSum += num % 10;
            num /= 10;
        }
        return digitSum;
    }
}

Was this solution helpful?