C++で1からNまでの総桁数を数える方法【初心者向け解説】

整数 N が入力として与えられ、1からNまでのすべての数値に含まれる桁数の合計を求めるのが本記事の目的です。桁数は数値の大きさに応じて増えていきます。具体的には、1〜9はそれぞれ1桁、10〜99はそれぞれ2桁、100〜999はそれぞれ3桁、というように10倍ごとに桁数が1つずつ増加します。

具体例を見てみましょう。

例1

• 入力： N = 11

• 出力： 1からNまでの合計桁数：13

• 説明： 1〜9は各1桁なので9桁、10と11は各2桁なので4桁。よって合計は 9 + 4 = 13桁 となります。

例2

• 入力： N = 999

• 出力： 1からNまでの合計桁数：2889

• 説明： 1〜9は各1桁で9桁、10〜99は各2桁で180桁、100〜999は各3桁で2700桁。よって合計は 9 + 180 + 2700 = 2889桁 となります。

アプローチ1：再帰を使った素朴な解法

まず基本的な方法として、再帰関数を使って各数値の桁数を順番に足し合わせていく手法を紹介します。数値 num を文字列に変換すると、その文字列の長さがそのまま桁数になります。これを num から 1 まで再帰的に繰り返すことで合計桁数を求めます。

アルゴリズムの手順

• 正の整数 num を入力として受け取ります。

• 関数 total_digits(int num) は、1からnumまでの合計桁数を返します。

• to_string(num) で num を文字列に変換します。

• 文字列の長さが num の桁数になります。

• num が 1 の場合は 1 を返し、それ以外は「桁数 + total_digits(num - 1)」を返して再帰的に処理します。

• 最終的に再帰全体の結果として合計桁数が得られます。

なお、この手法の計算量は O(N × 桁数) となるため、Nが大きい場合は非効率になる点に注意してください。

アプローチ2：10の累乗を利用した効率的な解法

より効率的な方法では、「各桁区切り（10、100、1000…）ごとに何個の数値が存在するか」をまとめて計算します。基準値 i（1, 10, 100, …）に対して、i 以上 num 以下の数値の個数は (num - i + 1) 個であり、それぞれが現在の桁数ぶん寄与するという考え方を利用します。

アルゴリズムの手順

• 正の整数 num を入力として受け取ります。

• 合計カウント count を 0 で初期化します。

• i を 1 から始めて、ループごとに10倍（i *= 10）しながら i <= num の間、count に (num - i + 1) を加算していきます。

• ループ終了後、count を結果として返します。

この手法の計算量は O(log₁₀N) であり、Nが非常に大きい場合でも高速に動作します。

実装例（素朴な解法）

#include <bits/stdc++.h>
using namespace std;
int total_digits(int num){
   string str = to_string(num);
   int length = str.length();
   if (num == 1){
      return 1;
   }
   return length + total_digits(num - 1);
}
int main(){
   int num = 20;
   cout<<"1からnまでの合計桁数："<<total_digits(num);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

1からnまでの合計桁数：31

実装例（効率的な解法）

#include <bits/stdc++.h>
using namespace std;
int total_digits(int num){
   int count = 0;
   for(int i = 1; i <= num; i *= 10){
      count = count + (num - i + 1);
   }
   return count;
}
int main(){
   int num = 20;
   cout<<"1からnまでの合計桁数："<<total_digits(num);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

1からnまでの合計桁数：31

まとめ

1からNまでの総桁数を求める問題では、再帰と文字列変換を用いたシンプルな解法でも正しい結果が得られますが、Nが大きくなると処理時間が課題になります。10の累乗を基準に桁の区切りごとに個数を数える効率的な解法を使えば、O(log₁₀N) の計算量で高速に答えを求められます。実際の開発や競技プログラミングでは、後者のアプローチを採用することをおすすめします。