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

पायथन में सबसे बड़े सबसेट की लंबाई खोजने का प्रोग्राम जहां हर जोड़ी में एक तत्व दूसरे से विभाज्य हो


मान लीजिए हमारे पास nums नामक यूनिक संख्याओं की एक लिस्ट है, हमें सबसे बड़ा सबसेट ढूंढना है जैसे कि सबसेट में हर जोड़ी (i, j) या तो i % j = 0 या j % i = 0 को संतुष्ट करे। हमें इस सबसेट का आकार ढूंढना है।

उदाहरण के लिए, यदि इनपुट nums = [3, 6, 12, 24, 26, 39] है, तो आउटपुट 4 होगा, क्योंकि सबसे बड़ा वैध सबसेट [3, 6, 12, 24] है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:

  • dp := nums के आकार की लिस्ट, 1 से भरी हुई
  • nums लिस्ट को सॉर्ट करें
  • n := nums का आकार
  • यदि n <= 1 है, तो n लौटाएं
  • ans := 0
  • i को 1 से n-1 तक लूप चलाएं:
    • j को 0 से i-1 तक लूप चलाएं:
      • यदि nums[i], nums[j] से विभाज्य है, तो dp[i] := max(dp[i], dp[j] + 1)
    • ans := max(ans, dp[i])
  • ans लौटाएं

पायथन कार्यान्वयन

class Solution:
    def solve(self, nums):
        dp = [1] * len(nums)
        nums.sort()
        n = len(nums)
        if n <= 1:
            return n
        ans = 0
        for i in range(1, n):
            for j in range(0, i):
                if nums[i] % nums[j] == 0:
                    dp[i] = max(dp[i], dp[j] + 1)
            ans = max(ans, dp[i])
        return ans

ob = Solution()
nums = [3, 6, 12, 24, 26, 39]
print(ob.solve(nums))

इनपुट

[3, 6, 12, 24, 26, 39]

आउटपुट

4
  1. पायथन में n-ary ट्री में सबसे लंबे पथ की लंबाई खोजने का प्रोग्राम पायथन में n-ary ट्री में सबसे लंबे पथ की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक एज लिस्ट है जहां प्रत्येक आइटम (u, v) रखता है जो दर्शाता है कि u, v का पैरेंट है। हमें ट्री में सबसे लंबे पथ की लंबाई ढूंढनी है। पथ की लंबाई 1 + उस पथ में नोड्स की संख्या है। उदाहरण के लिए, यदि इनपुट है: तो आउटपुट 5 होगा, क्योंकि पथ [1, 4, 5, 7] है, कुल 4 नोड्स हैं, इसलिए पथ

  1. Python प्रोग्राम से ऐरे में सबसे बड़ा तत्व खोजना Python प्रोग्राम से ऐरे में सबसे बड़ा तत्व खोजना

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक ऐरे दिया गया है, हमें ऐरे के सबसे बड़े तत्व की गणना करने की आवश्यकता है। यहां हम ब्रूट-फोर्स दृष्टिकोण का उपयोग करते हैं जिसमें हम पूरे लूप को पार करके और तत्व प्राप्त करके सबसे बड़ा तत्व निकालते हैं। हम नीच

  1. पायथन प्रोग्राम: ऐरे में सबसे बड़ा एलिमेंट ढूंढें पायथन प्रोग्राम: ऐरे में सबसे बड़ा एलिमेंट ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट इनपुट के रूप में एक ऐरे दिए जाने पर, हमें ऐरे में सबसे बड़ा एलिमेंट ढूंढने की आवश्यकता है। दृष्टिकोण हम max को पहले एलिमेंट के रूप में इनिशियलाइज़ करते हैं। इसके बाद, हम दिए गए ऐरे