অ্যারে থেকে ২, ৩, ৫ দ্বারা বিভাজ্য সর্বোচ্চ সংখ্যা বের করা (C++)

সমস্যা বিবরণ

একটি অ্যারে দেওয়া আছে যাতে শুধু একক অঙ্ক (0-9) রয়েছে। আমাদের কাজ হল এই অঙ্কগুলো দিয়ে ২, ৩ এবং ৫ — তিনটির দ্বারা বিভাজ্য সর্বোচ্চ সংখ্যা বের করা।

উদাহরণ

ইনপুট: arr[] = {1, 0, 5, 2}
আউটপুট: 510
ব্যাখ্যা: 510, ২, ৩, ৫ দ্বারা বিভাজ্য।

সমাধানের পদ্ধতি

২ এবং ৫ দ্বারা বিভাজ্য হলে সংখ্যাটি ১০ দ্বারা বিভাজ্য হবে, তাই অ্যারেতে ০ থাকতে হবে। ০কে শেষে রেখে বাকি অঙ্কগুলো নিম্নক্রমে সাজাতে হবে যেন ৩ দ্বারা বিভাজ্য হয়।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

string largestMultipleOfThree(vector<int>& d) {
    vector<vector<int>> mod(3);
    int sum=0;
    for(int x:d){ mod[x%3].push_back(x); sum+=x; sum%=3; }
    if(sum){
        if(mod[sum].empty()){
            int rem=3-sum;
            if(mod[rem].size()<2) return "";
            mod[rem].pop_back(); mod[rem].pop_back();
        }else mod[sum].pop_back();
    }
    string ret;
    for(int i=0;i<3;i++) for(int x:mod[i]) ret+=to_string(x);
    sort(ret.begin(), ret.end(), greater<>());
    if(!ret.empty() && ret[0]=='0') return "0";
    return ret;
}

int main() {
    vector<int> v={7,2,0,8};
    sort(v.begin(), v.end(), greater<>());
    if(v.back()!=0) cout<<"Not Possible";
    else cout<<largestMultipleOfThree(v);
    return 0;
}