C++에서 2, 3, 5의 가장 큰 배수 찾기

이 문제에서는 한 자리 숫자로만 구성된 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으로 나눌 수 있는 숫자를 생성하려면 배열이 0이어야 합니다.

0이 있으면 끝에 0을 사용하여 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