Count Largest Group Leetcode Solution

Difficulty Level Easy
Frequently asked in Mercari
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 2839

The problem Count Complete Group Leetcode Solution provides us with an integer. We are required to find the sum of digits of each number between 1 and n (inclusive). We will then group the numbers with the same sum of digits and keep a count. Then we need to compute the number of groups with the maximum count. This seems confusing at first. So, let’s take a look at a few examples.

Examples

Count Largest Group Leetcode Solution

n = 13
4

Explanation: The numbers grouped as per the sum of their digits are [1, 10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. So, there are 4 groups having the maximum frequency of 2. Hence the answer, 4.

n = 2
2

Explanation: Similarly, if you see the numbers until 2. There are only 2 numbers, 1, and 2. Both create a group having a single number each. Thus the answer is 2 groups that have a maximum frequency of 1.

Approach

The problem Count Largest Group Leetcode Solution provided us with a single integer. And asked to count the number of groups of numbers having the maximum frequency where we group the numbers as per their sum of digits. Since the input is a constraint to a maximum of 10000. We create an array to keep the frequency of the sum of digits of numbers. The maximum size of the cnt array should be 36. Because the input with the maximum sum will be 36. So, we simulate the process of finding the sum of digits for each number from 1 to n. During the evaluation of frequency, we store the maximum frequency calculated until now. Now, we start a new loop and count the number of groups having a maximum frequency.

Code for Count Largest Group Leetcode Solution

C++ Code

#include <bits/stdc++.h>
using namespace std;

int sumDigits(int n){
    int sum = 0;
    while(n>0){
        sum += (n%10);
        n /= 10;
    }
    return sum;
}

int countLargestGroup(int n) {
    int cnt[37];
    memset(cnt, 0, sizeof cnt);
    int mx = 0;
    for(int i=0;i<=n;i++){
        int s = sumDigits(i);
        cnt[s]++;
        if(cnt[s] > mx)
            mx = cnt[s];
    }
    
    int ans = 0;
    for(int i=0;i<37;i++){
        if(cnt[i] == mx)
            ans++;
    }
    return ans;
}

int main(){
    cout<<countLargestGroup(13);
}

4

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    public static int sumDigits(int n){
        int sum = 0;
        while(n>0){
            sum += (n%10);
            n /= 10;
        }
        return sum;
    }

    public static int countLargestGroup(int n) {
        int cnt[] = new int[37];
        for(int i=0;i<37;i++)cnt[i] = 0;
        int mx = 0;
        for(int i=1;i<=n;i++){
            int s = sumDigits(i);
            cnt[s]++;
            if(cnt[s] > mx)
                mx = cnt[s];
        }

        int ans = 0;
        for(int i=0;i<37;i++){
            if(cnt[i] == mx)
                ans++;
        }
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.print(countLargetGroup(13));
    }
    
}
4

Complexity Analysis

Time Complexity

O(N), because the first loop runs depends on the input. Thus the time complexity is linear.

Space Complexity

O(1), since we have a constant size array. Thus the space complexity remains constant irrespective of the input.

Translate »