C++ এ সবচেয়ে বড় বিভাজ্য উপসেট

ধরুন আমাদের কাছে স্বতন্ত্র ধনাত্মক পূর্ণসংখ্যার একটি সেট আছে, আমাদের সবচেয়ে বড় উপসেটটি খুঁজে বের করতে হবে যাতে এই উপসেটের উপাদানগুলির প্রতিটি জোড়া (Si, Sj) সন্তুষ্ট হয়:Si mod Sj =0 বা Sj mod Si =0।

সুতরাং ইনপুট যদি [1,2,3] এর মত হয়, সম্ভাব্য ফলাফল [1,2] বা [1,3] এর মত আসতে পারে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি অ্যারে ret তৈরি করুন, শেষ পয়েন্ট সেট করুন :=0, retLen :=1, n :=সংখ্যার আকার

• যদি n 0 হয়, তাহলে খালি সেট ফেরত দিন

• সংখ্যা অ্যারে সাজান

• দুটি অ্যারে লেন এবং n আকারের সমান তৈরি করুন, লেনকে 1 দিয়ে শুরু করুন এবং 0 দিয়ে সমান করুন

• 1 থেকে n – 1

  রেঞ্জের জন্য i

  • par[i] :=i

  • j-এর জন্য 0 থেকে i – 1

    পরিসরে

    • যদি nums[i] mod nums[j] =0 এবং len[j] + 1> len[i] হয়, তাহলে

      • len[i] :=len[j] + 1

      • par[i] :=j

  • যদি len[j]> retLen হয়, তাহলে retLen :=len[i] এবং এন্ডপয়েন্ট :=i

• ret এ nums[endPoint] ঢোকান

• যখন এন্ডপয়েন্ট par[endPoint]

  এর মতো নয়

  • এন্ডপয়েন্ট :=par[endPoint]

  • ret এ nums[endPoint] ঢোকান

• তালিকাটি উল্টে দিন এবং রিটার্ন রিটার্ন করুন

উদাহরণ(C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> largestDivisibleSubset(vector<int>& nums) {
      vector <int> ret;
      int endPoint = 0;
      int retLen = 1;
      int n = nums.size();
      if(!n) return {};
      sort(nums.begin(), nums.end());
      vector <int> len(n, 1);
      vector <int> par(n, 0);
      for(int i = 1; i < n; i++){
         par[i] = i;
         for(int j = 0; j < i; j++){
            if(nums[i] % nums[j] == 0 && len[j] + 1 > len[i]){
               len[i] = len[j] + 1;
               par[i] = j;
            }
         }
         if(len[i] > retLen){
            retLen = len[i];
            endPoint = i;
         }
      }
      ret.push_back(nums[endPoint]);
      while(endPoint != par[endPoint]){
         endPoint = par[endPoint];
         ret.push_back(nums[endPoint]);
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3};
   print_vector(ob.largestDivisibleSubset(v));
}

ইনপুট

[1,2,3]

আউটপুট

[1, 2, ]