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 iint 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 codepublic 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 sumdef 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 groupdef 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 Coden = 13group = 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 ifunction 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 |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
