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

पायथन में अंकगणितीय अनुक्रम से हटाए गए पद को ढूंढना


मान लीजिए हमारे पास nums नामक एक ऐरे है जिसमें n-1 अंकगणितीय अनुक्रम पद हैं। nums के पहले या अंतिम तत्व को छोड़कर एक तत्व पहले हटा दिया गया था। हमें हटाई गई संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है nums = [5, 7, 11, 13], तो आउटपुट होगा 9 क्योंकि, आइटम फॉर्मूला 2i+5 का पालन करते हैं, तो i = 2 के लिए यह 2*2 + 5 = 9 होगा जो गायब है।

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

कॉमन डिफरेंस interval = (last - first) // n की गणना करें। फिर बाइनरी सर्च का उपयोग करके उस इंडेक्स को ढूंढें जहां nums[i] != first + interval * i। गायब मान first + interval * i है।

  • यदि लंबाई 2 है, तो औसत लौटाएं।
  • यदि पहले दो तत्व समान हैं, तो उस मान को लौटाएं।
  • interval = (upper - lower) // len(nums) की गणना करें।
  • बाइनरी सर्च का उपयोग करके विचलन ढूंढें: यदि nums[mid] != lower + interval * mid, तो जांचें कि क्या पिछला सही है (गायब मिला) अन्यथा बाएं खोजें।
  • अन्यथा दाएं खोजें।

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

def solve(nums):
    if len(nums) == 2:
        return sum(nums) // 2
    if nums[0] == nums[1]:
        return nums[0]
    lower = nums[0]
    upper = nums[-1]
    interval = (upper - lower) // len(nums)
    pointer = len(nums) // 2
    left = 0
    right = len(nums) - 1
    while left != right:
        if nums[pointer] != nums[0] + interval * pointer:
            if nums[pointer - 1] == nums[0] + interval * (pointer - 1):
                return nums[0] + interval * pointer
            else:
                right = pointer
                pointer = (left + right) // 2
        else:
            if right - left == 1:
                pointer = right
            else:
                left = pointer
                pointer = (left + right) // 2

nums = [5, 7, 11, 13]
print(solve(nums))

इनपुट

[5, 7, 11, 13]

आउटपुट

9

  1. - पायथन में संख्याओं की सूची से अंकगणितीय उपअनुक्रमों की संख्या गिनने का प्रोग्राम

    संख्याओं की सूची nums दी गई है। लंबाई ≥ 3 के अंकगणितीय उपअनुक्रमों (subsequences) की संख्या गिनें। अंकगणितीय अनुक्रम वह है जहां लगातार अंतर समान हो। उदाहरण इनपुट: nums = [6, 12, 13, 8, 10, 14] आउटपुट: 3 उपअनुक्रम: [6, 8, 10], [6, 10, 14], [12, 13, 14]। एल्गोरिदम (DP के साथ हैश मैप) dp = डिक्शनरी

  1. - पायथन में संख्याओं की सूची से सन्निकट अंकगणितीय अनुक्रमों की संख्या गिनने का प्रोग्राम

    संख्याओं की सूची nums दी गई है। लंबाई ≥ 3 के सन्निकट (contiguous) अंकगणितीय अनुक्रमों (subarrays) की संख्या गिनें। उदाहरण इनपुट: nums = [6, 8, 10, 12, 13, 14] आउटपुट: 4 अनुक्रम: [6,8,10], [8,10,12], [6,8,10,12], [12,13,14]। एल्गोरिदम (रैखिक स्कैन) count = 0 (वर्तमान अंकगणितीय स्ट्रीक की लंबाई - 2

  1. - पायथन प्रोग्राम सूची से N सबसे बड़े तत्व खोजने के लिए

    एक पूर्णांक सूची दी गई है, हमारा कार्य सूची में N सबसे बड़े तत्व ढूंढना है। उदाहरण इनपुट : [40, 5, 10, 20, 9] N = 2 आउटपुट: [40, 20] एल्गोरिदम चरण 1: एक पूर्णांक सूची और सबसे बड़ी संख्या की संख्या इनपुट करें। चरण 2: पहले सूची को N बार पार करें। चरण 3: प्रत्येक पारगमन में सबसे बड़ा मान ढूंढें और इसे