C++で4と7のみで構成される数列のn番目の要素を求める方法

この問題では、整数 N が与えられ、「4」と「7」の2種類の数字のみで構成される数列の n 番目の要素を求めることが課題となります。

対象となる数列は以下のとおりです。

4, 7, 44, 47, 74, 77, …

入出力例

入力

N = 4

出力

47

説明

数列は 4, 7, 44, 47, … と続くため、4番目の要素は「47」になります。

解法アプローチ

最もシンプルな解決策は、N 番目まで数列を順番に生成していくことです。この数列には明確な規則性があります。ある数の末尾が「7」であれば、その前後の数の末尾は必ず「4」になっています。

そこで、1番目と2番目の要素を出発点とし、漸化式によって残りの要素を順に求めていきます。まず、サイズ N+1 の配列 series を用意し、初期値を設定します。

series[1] = 4
series[2] = 7

続いて、3番目以降の各インデックス i に対して、次の規則で値を計算します。

i が奇数の場合：series[i] = series[i/2] * 10 + 4
i が偶数の場合：series[i] = series[(i/2) - 1] * 10 + 7

つまり、奇数番目の要素は「親となる要素を10倍して4を加えた値」、偶数番目の要素は「親となる要素を10倍して7を加えた値」に対応します。この計算を N 回繰り返した後、series[N] の値を返せば答えが得られます。

実装プログラム

#include <iostream>
using namespace std;

int findNthSeriesElement(int N) {
    int series[N+1];
    series[1] = 4;
    series[2] = 7;
    for (int i=3; i<=N; i++) {
        if (i%2 != 0)
            series[i] = series[i/2]*10 + 4;
        else
            series[i] = series[(i/2)-1]*10 + 7;
    }
    return series[N];
}

int main() {
    int N = 9;
    cout<<"The "<<N<<"th element of the array is "<<findNthSeriesElement(N);
    return 0;
}

出力結果

The 9th element of the array is 474

まとめ

この手法では、各要素を一度だけ計算すればよいため、時間計算量・空間計算量はともに O(N) となります。また、この数列は各要素が親要素から枝分かれする二分木構造とみなせるため、n+1 の2進表現を利用してビットごとに「0→4」「1→7」と対応させることで、さらに効率的に n 番目の要素を求める方法もあります。まずは本記事の漸化式ベースのアプローチが、仕組みの理解もしやすく実装も簡単なのでおすすめです。