Count Largest Group - Practice Coding Problems

Count Largest Group - Problem

You are given an integer n.

We need to group the numbers from 1 to n according to the sum of their digits. For example, the numbers 14 and 5 belong to the same group (digit sum = 5), whereas 13 and 3 belong to different groups (digit sums 4 and 3).

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

Input & Output

Example 1 — Basic Case

$ Input: n = 13

› Output: 1

💡 Note: Numbers 1-13 grouped by digit sum: {1:[1,10], 2:[2,11], 3:[3,12], 4:[4,13], 5:[5], 6:[6], 7:[7], 8:[8], 9:[9]}. Groups with digit sum 1,2,3,4 each have 2 elements (maximum), but only digit sum 4 has the maximum count of 2.

Example 2 — Small Input

$ Input: n = 2

› Output: 2

💡 Note: Numbers: {1:[1], 2:[2]}. Each group has size 1, which is the maximum. Two groups have this maximum size.

Example 3 — Larger Input

$ Input: n = 15

› Output: 1

💡 Note: Groups: {1:[1,10], 2:[2,11], 3:[3,12], 4:[4,13], 5:[5,14], 6:[6,15], 7:[7], 8:[8], 9:[9]}. Maximum group size is 2, and 6 groups have this size, but we return 6.

Constraints

1 ≤ n ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n=13, consider numbers 1 to 13

Group by Digit Sum

Group numbers with same digit sum together

Count Result

Find maximum group size and count how many groups have it

Key Takeaway

🎯 Key Insight: Group numbers by their digit sum, then count how many groups achieve the maximum size

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to group numbers by their digit sum and find how many groups have the maximum size. Best approach uses a hash map to count group frequencies efficiently. Time: O(n×d), Space: O(k) where d is digits per number and k is unique digit sums.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Frequency Count	O(n × d)	O(k)	Use hash map to count group sizes efficiently
Brute Force with Array	O(n × d)	O(s)	Use array to store group sizes, iterate through to find maximum

Hash Map Frequency Count — Algorithm Steps

For each number 1 to n, calculate digit sum
Use hash map to count frequency of each digit sum
Find maximum frequency
Count how many digit sums have maximum frequency

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Numbers

Calculate digit sum for each number 1 to n

Build Hash Map

Count frequency of each digit sum

Find Result

Find max frequency and count occurrences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DIGIT_SUM 100

int solution(int n) {
    // Array to simulate hash map (since digit sums are small)
    int digitSumCount[MAX_DIGIT_SUM + 1];
    memset(digitSumCount, 0, sizeof(digitSumCount));
    
    // Calculate digit sum for each number and count groups
    for (int num = 1; num <= n; num++) {
        int digitSum = 0;
        int temp = num;
        while (temp > 0) {
            digitSum += temp % 10;
            temp /= 10;
        }
        
        digitSumCount[digitSum]++;
    }
    
    // Find maximum group size
    int maxSize = 0;
    for (int i = 0; i <= MAX_DIGIT_SUM; i++) {
        if (digitSumCount[i] > maxSize) {
            maxSize = digitSumCount[i];
        }
    }
    
    // Count how many groups have maximum size
    int count = 0;
    for (int i = 0; i <= MAX_DIGIT_SUM; i++) {
        if (digitSumCount[i] == maxSize) {
            count++;
        }
    }
    
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × d)

n iterations to calculate digit sums, each taking O(d) time where d is number of digits

✓ Linear Growth

Space Complexity

O(k)

Hash map stores k unique digit sums, where k ≤ 9×log₁₀(n)

✓ Linear Space

28.4K Views

Medium Frequency

~12 min Avg. Time

423 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler