C++で2、3、5の倍数となる最大の数を求めるアルゴリズム

問題概要

この問題では、1桁の数字のみで構成されたサイズNの配列arr[]が与えられます。求めるのは、2、3、5のすべてで割り切れる最大の数です。

具体例で問題を確認してみましょう。

入力 : arr[] = {1, 0, 5, 2}
出力 : 510

説明 −

数値510は、2、3、5のすべてで割り切れます。

解法アプローチ

この問題へのシンプルなアプローチは、組み立てた数の割り切り性を基本的な条件から確認していくことです。

まず、ある数が2と5の両方で割り切れるということは、すなわち10で割り切れることを意味します。10の倍数を作るためには、配列に0が含まれている必要があります。

配列に0が存在する場合は、末尾に0を配置し、その上で3でも割り切れるような最大の数を構成します。3の倍数の判定は各桁の合計で行えるため、余りごとに数字を分類して最適な組み合わせを選ぶことで効率的に求められます。

この手法の詳細は「C++で3の倍数となる最大の数を求める」の記事で解説していますので、あわせて参考にしてください。

実装例

以下は、このソリューションの動作を示すサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string largestMultipleOfThree(vector<int>& digits) { 
        vector<vector<int>> d(3);
        int sum = 0;
        for (int i = 0; i < digits.size(); i++) {
            int x = digits[i];
            d[x % 3].push_back(digits[i]);
            sum += x;
            sum %= 3;
        }
        if (sum) {
            if (!d[sum].size()) {
                int rem = 3 - sum;
                if (d[rem].size() < 2)
                return ""; 
                d[rem].pop_back();
                d[rem].pop_back();
            }
            else {
                d[sum].pop_back();
            }
        }
        string ret = "";
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < d[i].size(); j++) {
                ret += to_string(d[i][j]);
            }
        }
        sort(ret.begin(), ret.end(), greater<int>());
        if (ret.size() && ret[0] == '0')
        return "0";
        return ret;
    }
};
int main(){ 
   Solution ob;
   vector<int> v = {7, 2, 0, 8};
   sort(v.begin(), v.end(), greater<int>()); 
   if(v[v.size() - 1 ] != 0){
      cout<<"Not Possible!";
   }
   else{
      cout<<"The largest number is "<<(ob.largestMultipleOfThree(v));
   }
}

出力結果

The largest number is 870

この例では、配列{7, 2, 0, 8}から末尾に0を置き、残りの数字で桁の合計が3の倍数になるように選ぶことで、最大の数「870」が得られています。配列に0が含まれない場合は、2と5の両方で割り切れる数が作れないため、「Not Possible!」と表示されます。