JavaScriptで1からnまでの整数に含まれる「1」の個数を数える方法

はじめに

本記事では、正の整数を引数として受け取り、1からその数までのすべての正の整数に登場する数字「1」の合計出現回数を求めるJavaScript関数を作成します。対象となる数値自体に「1」が含まれている場合は、その分もカウントに含めます。

問題の例

たとえば、入力として次の数値が与えられたとします。

const num = 31;

この場合、期待される出力は次のとおりです。

const output = 14;

これは、「1」が以下の数値に出現するためです。

1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 31

これらを順に確認すると、11だけは「1」を2つ含んでいるため、合計で14回カウントされることになります。

実装コード

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

const num = 31;

const countOnes = (num = 1) => {
   if(num <= 0){
      return 0
   };
   let sum = 0
   num += '';
   let helper = p => {
      let leftNum = 0
      let rightNum = 0
      let di = num[p]
      if(p > 0){
         leftNum = parseInt(num.slice(0, p))
      }
      if(p + 1 < num.length){
         rightNum = parseInt(num.slice(p + 1))
      }
      if(di > 1){
         sum += (leftNum + 1) * (10 ** (num.length - 1 - p))
      } else if(di == 0){
         sum += (leftNum) * (10 ** (num.length - 1 - p))
      } else {
         sum += (leftNum) * (10 ** (num.length - 1 - p)) + rightNum + 1
      }
   }
   for(let i = 0; i < num.length; i++){
      helper(i)
   };
   return sum;
};
console.log(countOnes(num));

コードの解説

このアルゴリズムのポイントは、数値を文字列に変換し、各桁ごとに「その桁で1が出現する回数」を数学的に計算している点です。注目している桁については、次の3つの情報を使用します。

• leftNum：注目桁より左側（上位）の数値
• rightNum：注目桁より右側（下位）の数値
• di：注目している桁の数字そのもの

そして、注目桁の値に応じて次のように場合分けして加算していきます。

• di が 1 より大きい場合：(leftNum + 1) × 10^(残りの桁数) を加算します。
• di が 0 の場合：leftNum × 10^(残りの桁数) を加算します。
• di がちょうど 1 の場合：leftNum × 10^(残りの桁数) に加え、右側の数値分である rightNum + 1 も加算します。

この手法なら、1からnまでの数値を一つずつ文字列化して調べることなく、桁数に比例した計算量だけで答えを導き出せるため、非常に大きな数値でも高速に処理できます。

出力結果

上記コードを実行すると、コンソールには次のように出力されます。

14

まとめ

本記事では、1からnまでの整数に含まれる「1」の総出現回数を求めるJavaScript関数を紹介しました。シンプルにループで各数値を調べる方法もありますが、桁ごとの貢献度を計算する今回のアプローチは、大きな数値に対しても効率的に動作する点が大きなメリットです。同様の考え方は「0〜9の各数字の出現回数を数える」問題にも応用できるので、ぜひマスターしておきましょう。