1399. Count Largest Group

UnknownView on LeetCode

Hash Table Math Counting

Time: O(n log n)

Space: O(1)

Intuition

Digit sum of numbers 1..n. Count which digit sum appears most frequently.

Algorithm

1Compute digit sum for each number 1..n.
2Frequency map. Return key with maximum frequency.

Common Pitfalls

•Maximum digit sum for n<=10^5 is at most 45 (99999). Simple iteration.

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?