1399. Count Largest Group

Description

You are given an integer n.

Each number from 1 to n is grouped according to the sum of its digits.

Return the number of groups that have the largest size.

 

Example 1:

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

Example 2:

Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.

 

Constraints:

• 1 <= n <= 104

 

Solutions

Solution: Hash Map

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const countLargestGroup = function (n) {
  const sumMap = new Map();
  let largestSize = 0;
  let result = 0;

  const getDigitsSum = num => {
    let result = 0;

    while (num) {
      result += num % 10;
      num = Math.floor(num / 10);
    }

    return result;
  };

  for (let num = 1; num <= n; num++) {
    const sum = getDigitsSum(num);
    const size = sumMap.get(sum) ?? 0;

    sumMap.set(sum, size + 1);
    largestSize = Math.max(size + 1, largestSize);
  }

  for (const size of sumMap.values()) {
    if (size === largestSize) result += 1;
  }

  return result;
};