C++で無限整数列のN番目の桁を効率的に求める方法

問題の概要

「12345678910111213...」のように無限に続く整数列を考えます。この数列のn番目の桁がどの数字になるかを求めるのが本記事の課題です。例えば、入力が11の場合、数列を並べると「123456789101112」となり、11番目の桁は「0」であるため、出力は0になります。

アルゴリズムの考え方

すべての数字を実際に並べて数えるのは非効率です。そこで、桁数ごとの数字の個数を利用し、n番目の桁がどの数に属するかを効率的に特定します。1桁の数(1〜9)は9個で合計9桁、2桁の数(10〜99)は90個で合計180桁、3桁の数(100〜999)は900個で合計2700桁というように、各桁数の寄与を順番に差し引いていくのがポイントです。

具体的な手順は以下の通りです。

• len(現在の桁数)を1、cnt(その桁数の数の個数)を9、start(その桁数の最初の数)を1として初期化する
• n > len * cnt の間、以下を繰り返す:
  • n から len * cnt を引く
  • cnt を10倍、start を10倍する
  • len を1増やす
• start に (n - 1) / len を加算し、対象となる数を特定する
• start を文字列 s に変換する
• s[(n - 1) mod len] を返す(その数の中で何桁目かを特定)

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int findNthDigit(int n) {
        lli len = 1;
        lli cnt = 9;
        lli start = 1;
        while(n > len * cnt){
            n -= len * cnt;
            cnt *= 10;
            start *= 10;
            len++;
        }
        start += (n - 1) / len;
        string s = to_string(start);
        return s[(n - 1) % len] - '0';
    }
};
main(){
    Solution ob;
    cout << (ob.findNthDigit(11));
}

入力

11

出力

0

処理の流れ(入力が11の場合)

初期状態は len=1、cnt=9、start=1 です。まず n=11 は len*cnt=9 より大きいため、n から9を引いて n=2 となり、cnt=90、start=10、len=2 に更新されます。次に n=2 は len*cnt=180 より小さいためループを抜けます。start に (2-1)/2=0 を加算しても start=10 のままです。最後に、文字列「10」の (2-1)%2=1 番目の文字は「0」なので、答えは0となります。

このアルゴリズムの計算量は桁数に対して対数時間 O(log n) であり、非常に大きな n に対しても高速に動作するのが特徴です。