C++で2・3・5のすべてで割り切れる最大の数を求める方法

このチュートリアルでは、配列内の数字を組み合わせて作ることができる数の中から、2・3・5のすべてで割り切れる最大の数を求めるプログラムをC++で作成します。

まずは、問題を解くための条件と手順を順番に見ていきましょう。

2・3・5の倍数になるための条件

ある整数が2・3・5のすべてで割り切れるためには、次の2つの条件を満たす必要があります。

• 末尾が0であること：2と5の公倍数は10の倍数なので、数の末尾は必ず0になります。
• 各桁の合計が3の倍数であること：3の倍数かどうかは、各桁の数字の総和で判定できます。

アルゴリズムの手順

1. 配列を初期化します。
2. 配列に0が含まれているかを確認します。0が存在しない場合は、どのように並べても条件を満たせないため「Not possible」を出力して終了します。
3. 配列を降順にソートします。
4. 全桁の合計を3で割った余り（sum % 3）を求めます。
5. 余りが0でない場合は、各桁を3で割った余りが合計の余りと一致する数字を、影響の少ない小さい桁（末尾側）から探して1つ削除します。
6. 該当する数字が見つからない場合は、目標の余りを「3 − 元の余り」に切り替え、その余りに一致する数字を2つ削除します。
7. 最後に、残ったすべての桁を先頭から順に出力します。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void findLargestDivibleNumber(int n, vector<int>& v){
    int flag = 0;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] == 0) {
            flag = 1;
        }
        sum += v[i];
    }
    if (!flag) {
        cout << "Not possible" << endl;
    } else {
        sort(v.begin(), v.end(), greater<int>());
        if (v[0] == 0) {
            cout << "0" << endl;
        } else {
            int flag = 0;
            int remainder = sum % 3;
            if (remainder != 0) {
                for (int i = n - 1; i >= 0; i--) {
                    if (v[i] % 3 == remainder) {
                        v.erase(v.begin() + i);
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) {
                    remainder = 3 - remainder;
                    int count = 0;
                    for (int i = n - 1; i >= 0; i--) {
                        if (v[i] % 3 == remainder) {
                            v.erase(v.begin() + i);
                            count++;
                            if (count >= 2) {
                                break;
                            }
                        }
                    }
                }
            }
            if (*v.begin() == 0) {
                cout << "0" << endl;
            } else {
                for (int i : v) {
                    cout << i;
                }
            }
        }
    }
}
int main() {
    int n = 9;
    vector<int> v{ 4, 5, 0, 3, 2, 4, 5, 6, 7 };
    findLargestDivibleNumber(n, v);
    return 0;
}

実行結果

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

765544320

処理の流れを確認

サンプル配列 {4, 5, 0, 3, 2, 4, 5, 6, 7} の場合、配列には0が含まれており、全桁の合計は36（3の倍数）です。そのため削除処理は行われず、降順にソートした「765544320」がそのまま出力されます。

なお、ソートにO(N log N)、余りの調整処理にO(N)の計算量がかかるため、このアルゴリズム全体の計算量はO(N log N)となります。可能な並び替えをすべて試す非現実的なアプローチと比べ、非常に効率的に答えを導けるのが大きなポイントです。

まとめ

本チュートリアルでは、剰余の性質を活かして、2・3・5のすべてで割り切れる最大の数を効率的に求める方法を解説しました。内容について質問がある場合は、ぜひコメント欄でお知らせください。