C++で1回のスワップ操作で作れる最大の偶数を求める方法

このチュートリアルでは、与えられた数字の桁をたった1回入れ替える（スワップする）だけで作れる最大の偶数を求めるプログラムを、C++で作成していきます。

数値が偶数かどうかは最後の桁で決まるため、「最後の桁」と「それ以外の位置にある偶数の桁」を入れ替えるのが基本の考え方です。それでは、具体的な手順を見ていきましょう。

アルゴリズムの手順

1. 対象となる数字を文字列形式で用意します。
2. 先頭の桁から順に走査し、最後の桁の値以下となる偶数の桁を探します。
3. 条件を満たす偶数の桁が見つかった時点で、走査を終了します。
4. 偶数の桁が1つも存在しない場合は、入れ替えができないため元の数字をそのまま返します。
5. 見つけた偶数の桁と最後の桁をswap関数で入れ替えます。
6. 入れ替え後の数字を結果として返します。

C++での実装例

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

string getLargestEvenNumber(string number, int n) {
    int even = INT_MAX, index;
    for (int i = 0; i < n - 1; i++) {
        // 偶数の桁を見つけたら値と位置を記録
        if ((number[i] - '0') % 2 == 0) {
            even = (number[i] - '0');
            index = i;
        }
        // 最後の桁以下の偶数が見つかれば探索を打ち切り
        if (even <= (number[n - 1] - '0')) {
            break;
        }
    }
    // 偶数の桁が存在しない場合は元の文字列をそのまま返す
    if (even == INT_MAX) {
        return number;
    }
    swap(number[index], number[n - 1]);
    return number;
}

int main() {
    string number = "15433";
    cout << getLargestEvenNumber(number, 5) << endl;
    return 0;
}

出力結果

上記のコードをコンパイルして実行すると、次の結果が出力されます。

15334

コードの解説

入力例「15433」で動きを確認してみましょう。最後の桁は「3」（奇数）です。先頭から走査すると、最初に見つかる偶数の桁は3番目の「4」ですが、「4」は最後の桁「3」より大きいため、ここで入れ替えると数値が小さくなってしまいます。そのため走査を続けますが、それ以降に偶数の桁は現れません。ループ終了時には最後に見つけた偶数「4」の位置が記録されており、これが入れ替えの対象となります。結果として「15334」という最大の偶数が得られます。

このアルゴリズムのポイントは次の2点です。

• 最後の桁より小さい偶数が見つかった場合：できるだけ左側（上位の桁）にあるものを選ぶことで、大きい数字を高位に移動させ、数値を最大化できます。
• すべての偶数の桁が最後の桁より大きい場合：どこを入れ替えても数値は減少するため、なるべく右側（下位の桁）の偶数と入れ替えることで減少を最小限に抑えます。

なお、元の数字がすでに偶数で終わっているケースや同じ数字が並ぶケースなど、エッジケースの扱いについては、実際の要件に応じて適宜調整してください。

まとめ

本記事では、1回のスワップ操作で作れる最大の偶数を求めるC++のプログラムを紹介しました。文字列を線形に走査するだけなので、計算量はO(n)と非常に効率的です。チュートリアルの内容についてご不明な点があれば、コメント欄でお気軽にお尋ねください。