JavaScriptで桁和が同じ数値をグループ化し、最大のグループの個数を求める方法

本記事では、正の整数 n を引数として受け取り、1 から n までの整数を「各桁の数字の合計（桁和）」が同じもの同士でグループ分けし、要素数が最大となるグループの個数を返す JavaScript 関数の作成方法を解説します。

問題の概要

関数には正の整数 n が渡されます。まず、1 から n までの各整数について桁和を求め、桁和が等しい数値どうしを同じグループにまとめます。そのうえで、各グループの要素数を調べ、最も要素数の多いグループのサイズと一致するグループがいくつ存在するかを返します。

入力例

const num = 15;

出力例

const output = 6;

グループの内訳

[1, 10], [2, 11], [3, 12], [4, 13], [5, 14], [6, 15], [7], [8], [9]

この例では、最大のグループサイズは 2 です。そのサイズを持つグループは [1, 10]・[2, 11]・[3, 12]・[4, 13]・[5, 14]・[6, 15] の 6 つあるため、戻り値は 6 となります。

一方、入力が 67 の場合は最大サイズのグループが 4 つ存在するため、出力は 4 になります。

実装コード

以下が実際のコードです。

const num = 67;

const countLargestGroup = (num = 1) => {
  // n が 1 桁の場合は、すべてのグループのサイズが 1 になるため n を返す
  if (num < 10) {
    return num;
  }

  let result = 0;
  let maxSize = 0;
  const map = {};

  // 1 から n までの各数値の桁和を求め、グループごとにカウントする
  for (let i = 1; i <= num; i++) {
    let current = i;
    let sum = 0;
    while (current > 0) {
      sum += current % 10;
      current = Math.floor(current / 10);
    }
    map[sum] = (map[sum] ?? 0) + 1;
  }

  // 最大サイズのグループがいくつあるかを集計する
  for (const key of Object.keys(map)) {
    if (map[key] === maxSize) {
      result++;
    } else if (map[key] > maxSize) {
      result = 1;
      maxSize = map[key];
    }
  }

  return result;
};

console.log(countLargestGroup(num));

コードの解説

1. 早期リターンによる特別ケースの処理

n が 10 未満の場合、1〜9 の各数値の桁和はその数自身と等しくなるため、すべてのグループのサイズは 1 になります。つまり、グループの個数はちょうど n 個なので、そのまま n を返すことで無駄な計算を省いています。

2. 桁和の計算とグループ化

ループ内では、剰余演算子（% 10）を使って一の位を取り出して加算し、Math.floor() で 10 で割って桁をひとつ削る、という処理を繰り返すことで桁和を求めています。求めた桁和をオブジェクト map のキーとして出現回数を記録することで、同じ桁和を持つ数値が自然とグループ化されていきます。

3. 最大サイズのグループ数の集計

すべての数値の処理が完了したら、Object.keys() で map のキー（桁和）を順に走査します。現在の最大サイズ maxSize と同じ要素数のグループが見つかれば result をインクリメントし、さらに大きいグループが見つかった場合は result を 1 にリセットして maxSize を更新します。この処理により、最終的に「最大サイズを持つグループの個数」が result に格納されます。

実行結果

コンソールには次のように出力されます。

4

入力が 67 の場合、桁和ごとのグループのうち最大のサイズは 7 であり、該当するのは桁和が 6・7・8・9 となる 4 つのグループです。したがって、出力は 4 になります。

計算量について

時間計算量は O(n × d)（d は各数値の桁数）です。空間計算量は桁和の種類数に依存しますが、実際には桁和のパターンは高々数十個程度にしかならないため、メモリ使用量は非常に小さく抑えられます。