DDSA Solutions

1399. Count Largest Group

UnknownView on LeetCode
Hash TableMathCounting
Time: O(n log n)
Space: O(1)

Problem Overview

Digit sum of numbers 1..n.

Intuition

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

Algorithm

  1. 1Compute digit sum for each number 1..n.
  2. 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
C#
// 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?

Related Problems