C++でNより小さい「0と1のみで構成される数」を数える方法

問題概要

整数 N が入力として与えられたとき、N 未満の整数のうち、各桁が 0 と 1 のみで構成された数(いわゆる2進数のように見える数)がいくつあるかを求めるのが、この問題の目標です。
たとえば入力 N が 12 の場合、条件を満たすのは 1、10、11 の3つであるため、答えは 3 となります。

入出力例

例1

入力:

N=100

出力:

Nより小さい2進数字のみの数の個数 − 4

説明:

条件を満たす数は − 1, 10, 11, 100

例2

入力:

N=120

出力:

Nより小さい2進数字のみの数の個数: 7

説明:

条件を満たす数は: 1, 10, 11, 100, 101, 110, 111

プログラムのアプローチ

この手法では、整数型の vector「vec」を使用します。まず vec に 1 を push します。次の2進数的な数を生成するには、vec の末尾の数(temp、初期値は 1)を取り出し、temp×10 と temp×10+1 を新しい候補として追加していきます。これは、該当する数が必ず 1, 10, 11, 100, 110, 111 … という順序で並ぶためです。あとは vec から数を順に取り出し(pop)、その数が N 以下であればカウントを増やしていきます。

アルゴリズムの手順

• 整数 N を入力として受け取ります。
• 関数 Smaller_N(int N) が N を受け取り、条件を満たす数の個数を返します。
• カウント変数を 0 で初期化します。
• 0 と 1 のみを含む整数を格納するために、整数型の vector「vec」を用意します。
• vec.push_back(1) によって 1 を vector に追加します。
• while ループで vec を走査し、最後に push された要素を temp=vec.back() として取得し、vec から削除します。
• temp<=N であればカウントを +1 し、次の2進数的な整数として temp*10 と temp*10+1 を生成して vec に追加します。
• while ループが終了したら、カウントを結果として返します。

この方法は幅優先探索(BFS)のようなイメージで数を順次生成していくため、N を超えた候補はそれ以降展開されず、探索が自然に打ち切られる点がポイントです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int Smaller_N(int N){
    int count = 0;
    vector<int> vec;
    vec.push_back(1);
    while (!vec.empty()){
        int temp = vec.back();
        vec.pop_back();
        if (temp <= N){
            count++;
            int temp_2 = temp * 10;
            vec.push_back(temp_2);
            vec.push_back(temp_2 + 1);
        }
    }
    return count;
}
int main(){
    int N = 1000;
    cout<<"Count of Binary Digit numbers smaller than N are: "<<Smaller_N(N);
    return 0;
}

出力

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

Count of Binary Digit numbers smaller than N are: 8

まとめ

vector をキューのように使うことで、「0 と 1 のみで構成される数」を小さい順に効率よく生成し、N との比較だけで個数を求められます。桁が 0 と 1 しかないという性質を活かした、シンプルで分かりやすいアルゴリズムと言えるでしょう。