C++で1からnまでの「0」と「1」のみを含む整数の個数を求める方法

問題の概要

ある数値 n が与えられたとき、1からnまでの整数の中に、「0」と「1」のみで構成される数がいくつあるかを求めることを考えます。例えば、n = 15 の場合、条件を満たすのは「1」「10」「11」の3つであるため、答えは3となります。

解法のアプローチ

この問題は、再帰関数を使って「0」と「1」だけで作れる整数を順番に生成していくことで、効率的に解くことができます。現在の値 p に対して、末尾に「0」を追加した値（p × 10）と、末尾に「1」を追加した値（p × 10 + 1）の2方向へ再帰的に探索を進め、p が n を超えた時点で探索を打ち切るのがポイントです。

C++での実装例

#include<iostream>
using namespace std;
int numberOfValues(int p, int n) {
    if (p > n)
        return 0;
    return 1 + numberOfValues(p * 10, n) + numberOfValues(p * 10 + 1, n);
}
int main() {
    int n = 120;
    cout << "Number of values using 0s and 1s: " << numberOfValues(1, n);
}

実行結果

Number of values using 0s and 1s: 7

コードの解説

関数 numberOfValues(p, n) は、現在生成中の数 p が n を超えた場合に 0 を返します。それ以外の場合は、p 自身が条件を満たす有効な数であることを表す「1」と、p の末尾に「0」を付けた数（p × 10）、「1」を付けた数（p × 10 + 1）それぞれについての再帰呼び出しの結果を合計して返します。

n = 120 の場合、条件を満たす数は「1」「10」「11」「100」「101」「110」「111」の7個となるため、出力は7になります。この手法では、条件に関係のない数を一切調べることなく、必要な数だけを直接生成できるため、1からnまでを全件チェックする方法よりもはるかに効率的です。