This post is completed by 2 users

  • 2
 Add to List
Medium

544. Counting the Largest Number Groups by Digit Sum

Given a positive integer N, the task is to group the numbers from 1 to N based on the sum of their digits. Each number will belong to a group determined by its digit sum. The objective is to write a program that counts the number of groups that are the largest in size.

Example: 
Example 1:
Given N = 15, our objective is to find the count of the largest number groups.
Output: 6
Groups: [1, 10], [2, 11], [3, 12], [4, 13], [5, 14], [6, 15], [7], [8], [9]
In this case, there are six groups of size 2.

Example 2:
For N = 4, the goal remains the same.
Output: 4
Groups: [1], [2], [3], [4]
Here, there are four groups of size 1.
Solution: Use Map

  1. Initialize a Map<Integer, Integer> named 'map' to store the digit sum as the key and the count of numbers with that sum as the value.

  2. Initialize the variable 'largestGroupSize' to keep track of the largest group size encountered.

  3. Iterate from 1 to N and perform the following for each number:

    1. Calculate the sum of the digits by iteratively dividing the number by 10 and summing up the remainders.

    2. Retrieve the current count associated with the sum from the map using 'getOrDefault'.

    3. c. Increment the count in the map by one.

  4. d. Update 'largestGroupSize' to the maximum value between its current value and the updated count.


See the code below for more understanding.

Output:

6

Reference: leetcode

Related Problems: