C++でN以下のすべての桁が偶数となる最大の数を求める方法

はじめに

このチュートリアルでは、与えられた整数 n 以下の数のうち、すべての桁が偶数である最大の数を求めるプログラムをC++で作成します。例えば n = 43 の場合、「3」という奇数の桁を含むため条件を満たさず、答えは 42 となります。

解法のアプローチ

もっともシンプルな方法は、n から順に数を減らしながら各桁を調べていく力まかせ（ブルートフォース）な探索です。手順は以下の通りです。

• 整数 n を初期化します。
• i = n からループを開始します。
• 現在の数 i の各桁がすべて偶数かどうかを判定します。
• 条件を満たす場合は、その数を返して終了します。
• 満たさない場合は、i を1減らして再度チェックします。

桁の偶数判定の考え方

数値を10で割った余り（n % 10）で一の位の桁を取り出し、それが偶数かどうかを確認します。奇数の桁が見つかった時点で即座に判定を打ち切り、数を10で割りながら上位の桁へと順に調べていきます。

コード例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

// すべての桁が偶数かどうかを判定する関数
int allDigitsEven(int n) {
    while (n) {
        if ((n % 10) % 2) {
            return 0; // 奇数の桁が見つかった場合
        }
        n /= 10;
    }
    return 1; // すべての桁が偶数
}

// n以下で全桁が偶数の最大の数を見つける関数
int findLargestEvenNumber(int n) {
    int i = n;
    while (true) {
        if (allDigitsEven(i)) {
            return i;
        }
        i--;
    }
}

int main() {
    int N = 43;
    cout << findLargestEvenNumber(N) << endl;
    return 0;
}

実行結果

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

42

補足：計算量について

この方法は非常にシンプルですが、最悪の場合は答えに到達するまで1ずつ数を減らして調べることになります。ただし、全桁が偶数の数は比較的密に存在する（例えば下2桁だけでも 00, 02, 04, … 88 など多数存在する）ため、実際にはすぐに答えが見つかることがほとんどです。

まとめ

本チュートリアルでは、n 以下の数のうちすべての桁が偶数である最大の数を求める方法を学びました。桁ごとの判定ロジックと単純な探索ループを組み合わせるだけで、この問題は簡単に解決できます。チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。