Tìm bội số lớn nhất của 2, 3 và 5 trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước N chỉ gồm các chữ số đơn lẻ. Nhiệm vụ của chúng tôi là tìm bội số lớn nhất của 2, 3 và 5 .

Hãy lấy một ví dụ để hiểu vấn đề,

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

Giải thích -

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là kiểm tra tính chất chia hết cơ bản của số được tạo.

Vì vậy, nếu số cần chia hết cho 2 và 5 tức là số đó chia hết cho 10. Để tạo số chia hết cho 10, mảng phải có số không.

Nếu nó có số 0 thì chúng ta sẽ tạo ra số lớn nhất có thể có số 0 ở cuối chia hết cho 3.

Phương pháp được hiển thị ở đây. Nhiều nhất trong số ba trong C ++

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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));
   }
}

Đầu ra

The largest number is 870