Count of groups having largest size while grouping according to sum of its digits

Last Updated : 12 Sep, 2022

Given an integer N, the task is to find the number of groups having the largest size. Each number from 1 to N is grouped according to the sum of its digits.

Examples:

Input: N = 13
Output: 4
Explanation:
There are 9 groups in total, they are grouped according to the sum of its digits of numbers from 1 to 13: [1, 10] [2, 11] [3, 12] [4, 13] [5] [6] [7] [8] [9].
Out of these, 4 groups have the largest size that is 2.

Input: n = 2
Output: 2
Explanation:
There are 2 groups in total. [1] [2] and both the groups have largest size 1.

Approach: To solve the problem mentioned above we need to create a dictionary whose key represents the unique sum of digits of numbers from 1 to N. The values of those keys will keep count how many numbers have the sum equal to its key. Then we will print the highest value among all of them.

Below is the implementation of the above approach:

C++

// C++ implementation to Count the 
// number of groups having the largest 
// size where groups are according 
// to the sum of its digits 
#include <bits/stdc++.h> 
using namespace std;
 
// function to return sum of digits of i
int sumDigits(int n){
    int sum = 0;
    while(n)
    {
        sum += n%10;
        n /= 10;
    }
 
    return sum;
}
 
// Create the dictionary of unique sum 
map<int,int> constDict(int n){
     
    // dictionary that contain 
    // unique sum count 
    map<int,int> d;
 
    for(int i = 1; i < n + 1; ++i){ 
        // calculate the sum of its digits 
        int sum1 = sumDigits(i);
 
        if(d.find(sum1) == d.end())
            d[sum1] = 1;
        else
            d[sum1] += 1;        
    }
 
    return d;
}
 
// function to find the 
// largest size of group 
int countLargest(int n){
     
    map<int,int> d = constDict(n);
     
    int size = 0;
 
    // count of largest size group 
    int count = 0;
 
    for(auto it = d.begin(); it != d.end(); ++it){
        int k = it->first;
        int val = it->second;
 
        if(val > size){            
            size = val;
            count = 1;
        }
        else if(val == size)            
            count += 1;
    }
 
    return count;
}
     
// Driver code 
int main() 
{ 
    int    n = 13;
 
    int group = countLargest(n); 
 
    cout << group << endl;
 
    return 0; 
}

Java

// Java implementation to Count the  
// number of groups having the largest  
// size where groups are according  
// to the sum of its digits 
import java.util.HashMap;
import java.util.Map;
 
class GFG{
     
// Function to return sum of digits of i 
public static int sumDigits(int n)
{ 
    int sum = 0; 
    while(n != 0) 
    { 
        sum += n % 10; 
        n /= 10; 
    } 
   
    return sum; 
} 
   
// Create the dictionary of unique sum  
public static HashMap<Integer, Integer> constDict(int n)
{ 
     
    // dictionary that contain  
    // unique sum count  
    HashMap<Integer, Integer> d = new HashMap<>(); 
     
    for(int i = 1; i < n + 1; ++i)
    {
         
        // Calculate the sum of its digits  
        int sum1 = sumDigits(i); 
   
        if (!d.containsKey(sum1)) 
            d.put(sum1, 1); 
        else
            d.put(sum1, d.get(sum1) + 1); 
    } 
    return d; 
} 
   
// Function to find the  
// largest size of group  
public static int countLargest(int n)
{ 
    HashMap<Integer, Integer> d = constDict(n);  
       
    int size = 0; 
   
    // Count of largest size group  
    int count = 0; 
 
    for(Map.Entry<Integer, Integer> it : d.entrySet())
    {
        int k = it.getKey(); 
        int val = it.getValue(); 
         
        if (val > size)
        {             
            size = val; 
            count = 1; 
        } 
        else if (val == size)             
            count += 1; 
    } 
   
    return count; 
} 
 
// Driver code
public static void main(String[] args)
{
    int n = 13; 
    int group = countLargest(n);  
   
    System.out.println(group);
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 implementation to Count the
# number of groups having the largest 
# size where groups are according 
# to the sum of its digits
 
# Create the dictionary of unique sum
def constDict(n):
     
    # dictionary that contain
    # unique sum count
    d ={} 
 
    for i in range(1, n + 1):
         
        # convert each number to string
        s = str(i) 
         
        # make list of number digits
        l = list(s) 
         
        # calculate the sum of its digits
        sum1 = sum(map(int, l)) 
 
        if sum1 not in d:
            d[sum1] = 1
             
        else:
            d[sum1] += 1
                     
    return d
     
# function to find the
# largest size of group
def countLargest(n):
     
    d = constDict(n)
     
    size = 0
 
    # count of largest size group
    count = 0
 
    for k, val in d.items():
         
        if val > size:
             
            size = val
            count = 1
             
        elif val == size:
             
            count += 1
 
    return count
     
# Driver Code
n = 13
group = countLargest(n)
print(group)
 
# This code is contributed by Sanjit_Prasad

C#

// C# implementation to Count the  
// number of groups having the largest  
// size where groups are according  
// to the sum of its digits 
using System;
using System.Collections.Generic; 
class GFG {
     
    // Function to return sum of digits of i 
    static int sumDigits(int n)
    { 
        int sum = 0; 
        while(n != 0) 
        { 
            sum += n % 10; 
            n /= 10; 
        } 
        
        return sum; 
    } 
        
    // Create the dictionary of unique sum  
    static Dictionary<int, int> constDict(int n)
    { 
          
        // dictionary that contain  
        // unique sum count  
        Dictionary<int, int> d = new Dictionary<int, int>(); 
          
        for(int i = 1; i < n + 1; ++i)
        {
              
            // Calculate the sum of its digits  
            int sum1 = sumDigits(i); 
        
            if (!d.ContainsKey(sum1)) 
                d.Add(sum1, 1); 
            else
                d[sum1] += 1;
        } 
        return d; 
    } 
        
    // Function to find the  
    // largest size of group  
    static int countLargest(int n)
    { 
        Dictionary<int, int> d = constDict(n);  
            
        int size = 0; 
        
        // Count of largest size group  
        int count = 0; 
         
        foreach(KeyValuePair<int, int> it in d) 
        { 
            int k = it.Key; 
            int val = it.Value; 
              
            if (val > size)
            {             
                size = val; 
                count = 1; 
            } 
            else if (val == size)             
                count += 1; 
        } 
        
        return count; 
    }   
   
  // Driver code
  static void Main() 
  {
    int n = 13; 
    int group = countLargest(n);  
    Console.WriteLine(group);
  }
}
 
// This code is contributed by divyesh072019

Javascript

// JS implementation to Count the 
// number of groups having the largest 
// size where groups are according 
// to the sum of its digits 
 
 
// function to return sum of digits of i
function sumDigits(n){
    let sum = 0;
    while(n > 0)
    {
        sum += n%10;
        n = Math.floor(n / 10);
    }
 
    return sum;
}
 
// Create the dictionary of unique sum 
function constDict( n){
     
    // dictionary that contain 
    // unique sum count 
    let d = {};
 
    for(var i = 1; i < n + 1; ++i){ 
        // calculate the sum of its digits 
        var sum1 = sumDigits(i);
 
        if(!d.hasOwnProperty(sum1))
            d[sum1] = 1;
        else
            d[sum1] += 1;        
    }
 
    return d;
}
 
// function to find the 
// largest size of group 
function countLargest( n){
     
    let d = constDict(n);
     
    let size = 0;
 
    // count of largest size group 
    let count = 0;
     
    for (let [k, val] of Object.entries(d))
    {
        k = parseInt(k)
        val = parseInt(val)
 
        if(val > size){            
            size = val;
            count = 1;
        }
        else if(val == size)            
            count += 1;
    }
 
    return count;
}
    
     
// Driver code 
let n = 13;
 
let group = countLargest(n); 
 
console.log(group);
 
 
// This code is contributed by phasing17