C++で1・2・3・4の4種類の数字から構成される数列のn番目の数の桁数を求める方法

この記事では、与えられた4つの数字「1、2、3、4」のみを使って構成される数列の中から、n番目の数の桁数を求める問題について解説します。

これらの数字だけで作られる数列は、以下のように並びます。

1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24...

このパターンを注意深く観察すると、次のような規則性が見えてきます。

• 1桁の数は4個存在します（1、2、3、4）。
• 2桁の数は16個存在します（11〜44）。
• この傾向は4の累乗として続いていきます。

具体例

入力

7

出力

2

数列の7番目の数は「13」であり、その桁数は2桁です。

アルゴリズム

手順は以下の通りです。

1. 対象となる数nを初期化します。
2. 結果を格納する変数と、各グループの個数の累積和を格納する変数の2つを用意します。
3. 反復変数を4の累乗ずつ増やしながらループ処理を行います。
   • 現在の値を累積和の変数に加算します。
   • 累積和がn以上になった時点でループを抜けます。
   • 次のグループの数は前のグループより1桁多くなるため、結果に1を加算します。
4. 最終的な結果を返します。

このアルゴリズムの計算量はO(log₄ n)となり、非常に効率的に桁数を求められます。

C++での実装

以下は、上記アルゴリズムをC++で実装した例です。

#include <bits/stdc++.h>
using namespace std;
int getDigitsCount(int n) {
    int i, result = 1, sum = 0;
    for (i = 4; ; i *= 4) {
        sum += i;
        if (sum >= n) {
            break;
        }
        result += 1;
    }
    return result;
}
int main() {
    int n = 57;
    cout << getDigitsCount(n) << endl;
    return 0;
}

実行結果

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

3

n = 57の場合、数列の57番目の数は3桁であることがわかります。1桁の数が4個、2桁の数が16個あるため、20番目までは2桁以下となり、21番目以降が3桁になります。57番目は3桁の範囲内にあるため、正しく「3」が出力されます。