मान लीजिए हमारे पास विशिष्ट धनात्मक पूर्णांकों का एक समुच्चय है, हमें सबसे बड़ा उपसमुच्चय ढूंढना है जैसे कि इस उपसमुच्चय में (Si, Sj) जैसी हर जोड़ी के तत्व संतुष्ट करते हैं: Si mod Sj = 0 या Sj mod Si = 0।
उदाहरण के लिए, यदि इनपुट [1,2,3] जैसा है, तो संभावित परिणाम [1,2] या [1,3] जैसा आ सकता है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
retनामक एक सरणी बनाएं,endpoint := 0सेट करें,retLen := 1,n := nums का आकार- यदि
n = 0, तो खाली समुच्चय लौटाएं numsसरणी को सॉर्ट करें- आकार n के दो सरणी
lenऔरparबनाएं,lenको 1 से इनिशियलाइज़ करें, औरparको 0 से iको 1 सेn - 1तक लूप करेंpar[i] := ijको 0 सेi - 1तक लूप करें- यदि
nums[i] mod nums[j] = 0 और len[j] + 1 > len[i], तोlen[i] := len[j] + 1par[i] := j
- यदि
- यदि
len[j] > retLen, तोretLen := len[i]औरendpoint := i
nums[endPoint]कोretमें डालें- जब तक
endpoint, par[endPoint] के समान नहीं हैendpoint := par[endPoint]nums[endPoint]कोretमें डालें
retसूची को उल्टा करें और लौटाएं
उदाहरण (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, ]