【C++解説】4と7だけで構成される数列の中から、与えられた数字の位置を効率的に求める方法

この問題では、ある数字 N が与えられ、その数字が「4」と「7」のみで構成される数列の中で何番目に位置するかを求めることが課題となります。

4と7だけを使って作られる数列は、次のように並びます。

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

入力例と出力例

問題を理解するために、具体的な例を見てみましょう。

入力

N = 5

出力

74

説明

数列の5番目までの要素は次の通りです。

4, 7, 44, 47, 74…

つまり、5番目の数は 74 であることが分かります。

解法アプローチ：数列のパターンに着目する

この問題に対するシンプルかつ効率的な解法は、数列に潜む規則性(パターン)を見つけることに基づいています。

数列をよく観察すると、次のような特徴が見えてきます。

• 偶数番目の位置にある数は、必ず 7 で終わる。
• 奇数番目の位置にある数は、必ず 4 で終わる。

この性質を利用すると、与えられた数字を1桁ずつ処理しながら、現在の桁に応じて位置(position)を更新していくことで、目的の位置を求めることができます。

位置の更新ルールは以下の通りです。

• 現在の桁が 4 の場合:
  position = (position × 2) + 1
• 現在の桁が 7 の場合:
  position = (position × 2) + 2

実は、この仕組みは2進数の考え方と密接に関係しています。「4」を1、「7」を2に対応させると、各桁の並びがそのまま位置を表す2進数的な値になるため、桁数を d とすると O(d) の計算量で高速に答えを導き出せます。

ソリューションの実装例(C++)

それでは、この解法の動作を示すプログラムを見てみましょう。

サンプルコード

#include <iostream>
using namespace std;

int findNumPosition(string num){
    int i = 0, position = 0;
    while (num[i] != '\0') {
        position *= 2;
        if(num[i] == '4')
            position += 1;
        else
            position += 2;
        i++;
    }
    return position;
}

int main() {
    string num = "74774";
    cout<<"The position of the number in the series is "<<findNumPosition(num);
    return 0;
}

出力

The position of the number in the series is 53

コードの解説

findNumPosition 関数では、文字列として渡された数字を先頭の桁から順に走査します。

1. まず position を2倍します(既存の桁情報を1桁左にシフトするイメージ)。
2. 現在の桁が「4」なら1を加算、「7」なら2を加算します。
3. すべての桁を処理し終えた時点の position が、数列内での位置となります。

例えば「74774」の場合、各桁を順に処理することで最終的に 53 という位置が得られます。

まとめ

本記事では、4と7だけで構成される数列において、与えられた数字の位置を求める方法を紹介しました。数列の偶数・奇数番目の末尾の規則性に着目し、桁ごとに position × 2 + 1 または position × 2 + 2 で更新していくことで、線形時間 O(d) で効率よく解ける点がポイントです。