C++-এ অ্যারে অফ ডিজিট থেকে ৩-এর গুণিতক সর্বোচ্চ সংখ্যা বের করা (Set 2)

সমস্যা

ডিজিটের অ্যারে দেওয়া। কিছু ডিজিট কনক্যাটেনেট করে ৩-এর গুণিতক বানাতে হবে। সংখ্যাটি স্ট্রিং হিসেবে রিটার্ন করুন (খুব বড় হতে পারে)। সম্ভব না হলে খালি স্ট্রিং।

অ্যালগরিদম: মডুলো ৩ গ্রুপিং

1. ডিজিটগুলো ডিসেন্ডিং অর্ডারে সর্ট করুন।
2. মডুলো ৩ অনুযায়ী ৩টি গ্রুপে ভাগ করুন: d[0], d[1], d[2]।
3. সামান্য যোগফল sum % 3 বের করুন।
4. যদি sum % 3 != 0:
   • সেই মডুলোর গ্রুপে ডিজিট থাকলে একটা মুছুন।
   • নাহলে, অন্য গ্রুপ থেকে দুটি ডিজিট মুছুন (যেন মডুলো ৩ শূন্য হয়)।
5. বাকি ডিজিটগুলো কনক্যাটেনেট করুন, আবার ডিসেন্ডিং সর্ট করুন।
6. যদি ফলাফল "0" দিয়ে শুরু হয়, তবে "0" রিটার্ন করুন।

C++ কোড

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

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        vector<vector<int>> d(3);
        sort(digits.begin(), digits.end(), greater<int>());
        int sum = 0;
        for (int x : digits) {
            d[x % 3].push_back(x);
            sum = (sum + x) % 3;
        }
        if (sum) {
            if (d[sum].empty()) {
                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 x : d[i]) ret += to_string(x);
        sort(ret.begin(), ret.end(), greater<char>());
        if (!ret.empty() && ret[0] == '0') return "0";
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {7,2,8};
    cout << ob.largestMultipleOfThree(v); // 87
}

আউটপুট

87