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

पायथन में LCM अधिकतम K वाला ऐरे का सबसे लंबा सबसीक्वेंस खोजें


मान लीजिए हमारे पास n विभिन्न संख्याओं का एक ऐरे A है और एक और धनात्मक पूर्णांक K है, हमें ऐरे में सबसे लंबा सब-सीक्वेंस ढूंढना है जिसका लघुत्तम समापवर्त्य (LCM) अधिकतम K हो। उसके बाद LCM और सब-सीक्वेंस की लंबाई लौटाएं, प्राप्त सब-सीक्वेंस के तत्वों के इंडेक्स (0 से शुरू) के बाद। अन्यथा, -1 लौटाएं।

तो, यदि इनपुट A = [3, 4, 5, 6], K = 20 जैसा है, तो आउटपुट होगा: LCM = 12, लंबाई = 3, इंडेक्स = [0,1,3]

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • n := A का आकार

  • my_dict := एक मैप

  • i को 0 से n तक के लिए, करें:

    • my_dict[A[i]] := my_dict[A[i]] + 1

  • count := आकार (k+1) का एक ऐरे 0 से भरा हुआ

  • my_dict में प्रत्येक कुंजी के लिए, करें:

    • यदि कुंजी <= k, तो:

      • i := 1

      • जब कुंजी * i <= k, करें:

        • count[कुंजी * i] := count[कुंजी * i] + my_dict[कुंजी]

        • i := i + 1

    • अन्यथा,

      • लूप से बाहर निकलें

  • lcm := 0, size := 0

  • i को 1 से k+1 तक के लिए, करें:

    • यदि count[i] > size, तो:

      • size := count[i]

      • lcm := i

  • यदि lcm, 0 के समान है, तो:

    • -1 लौटाएं

  • अन्यथा,

    • lcm और size प्रदर्शित करें

    • i को 0 से n तक के लिए, करें:

      • यदि lcm mod A[i], 0 के समान है, तो:

        • i प्रदर्शित करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

from collections import defaultdict def get_seq(A,k):    n = len(A)    my_dict = defaultdict(lambda:0)    for i in range(0, n):       my_dict[A[i]] += 1    count = [0] * (k + 1)    for key in my_dict:       if key <= k:          i = 1          while key * i <= k:             count[key * i] += my_dict[key]             i += 1       else:          break    lcm = 0    size = 0    for i in range(1, k + 1):       if count[i] > size:          size = count[i]          lcm = i    if lcm == 0:       print(-1)    else:       print("LCM = {0}, Length = {1}".format(lcm, size))       print("Index values: ", end = "")       for i in range(0, n):          if lcm % A[i] == 0:             print(i, end = " ") k = 20 A = [3, 4, 5, 6] get_seq(A,k)

इनपुट

[3, 4, 5, 6] , 20

आउटपुट

LCM = 12, Length = 3 Index values: 0 1 3

  1. Python प्रोग्राम में ऐरे का योग खोजना Python प्रोग्राम में ऐरे का योग खोजना

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

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

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

  1. पायथन प्रोग्राम: ऐरे का योग ढूंढें पायथन प्रोग्राम: ऐरे का योग ढूंढें

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