This post is completed by 2 users

  • 2
 Add to List

Count Largest Groups

Given a number N, Each number is grouped as per the sum of the digits in the number. Write a program to count the groups which are largest in size.

Example: 
N = 15
Output: 6
Groups = [1, 10], [2, 11], [3, 12], [4, 13], [5, 14], [6, 15], [7], [8], [9] so there are 6 groups of size 2.

N = 4
Output: 4
Groups = [1], [2], [3], [4]  there are 4 groups of size 1
Solution:

Use Map

Construct the map with sum (of digits) as key and count (numbers which have that sum) as value. Iterate the number from 1 to N and for each number get the sum of its digit and construct the map and during iteration also keep track of the maximum count you have seen this will be the largest group size. Once the map is constructed, iterate the map and total entries which have the maximum count will be the count of largest groups.
See the code below for more understanding.

Code:


Output:

6

Reference: leetcode

Also Read: