Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सबसे बड़ा विभाज्य उपसमुच्चय


मान लीजिए हमारे पास विशिष्ट धनात्मक पूर्णांकों का एक समुच्चय है, हमें सबसे बड़ा उपसमुच्चय ढूंढना है जैसे कि इस उपसमुच्चय में (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] := 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] और 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, ]

  1. - C++ में सरणी में विभाज्य जोड़ों की गिनती करें

    हमें किसी भी आकार की एक सरणी दी गई है जिसमें पूर्णांक तत्व हैं और कार्य सरणी में जोड़ों की संख्या की गणना करना है जैसे कि एक जोड़ी का एक तत्व जोड़ी के दूसरे तत्व को विभाजित करता है। उदाहरण के लिए इनपुट - int arr[] = {1, 2, 3, 6} आउटपुट - गिनती 4 है व्याख्या - (1,2), (1,3), (1,6) और (3,6) वे जोड़े

  1. - C++ में तीन से विभाज्य महत्तम योग

    मान लीजिए हमारे पास पूर्णांकों की एक सरणी nums है, हमें दिए गए सरणी के तत्वों का अधिकतम संभव योग ढूंढना है जो तीन से विभाज्य हो। उदाहरण के लिए, यदि इनपुट [3,6,5,1,8] है, तो आउटपुट 18 होगा, क्योंकि उपसरणी [3,6,1,8] का योग 18 है, जो 3 से विभाज्य है।इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंग

  1. - C++ में K से विभाज्य उपसरणी योग

    मान लीजिए हमारे पास पूर्णांकों की एक सरणी A है। हमें सन्निकट गैर-खाली उपसरणी की संख्या ढूंढनी है जिनका योग k से विभाज्य है। यदि A = [4,5,0,-2,-3,1] और k = 5 है, तो आउटपुट 7 होगा। सात उपसरणी हैं: [[4,5,0,-2,-3,1], [5], [5,0],[5,0,-2,-3], [0], [0,-2,-3], [-2,-3]]हल करने के चरणएक मैप m बनाएं और m[0] को