C ++で2、3、5の最大の倍数を見つける

この問題では、1桁のみで構成されるサイズNの配列arr[]が与えられます。私たちの仕事は、 2、3、5の最大の倍数を見つけることです 。

問題を理解するために例を見てみましょう

Input : arr[] = {1, 0, 5, 2}
Output : 510

説明 −

The number 510 is divisible by all 2, 3, 5.

ソリューションアプローチ

この問題の簡単な解決策は、作成された数の基本的な除算性をチェックすることです。

したがって、数値を2と5で割り切れる必要がある場合、つまり10で割り切れる必要がある場合、10で割り切れる数値を作成するには、配列にゼロが必要です。

ゼロがある場合は、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