पायथन में तत्वों की लिस्ट से डुप्लिकेट आइटम ढूंढना

मान लीजिए हमारे पास nums नामक तत्वों की एक लिस्ट है जिसका आकार n + 1 है, उन्हें रेंज 1, 2, ..., n से चुना गया है। जैसा कि हम जानते हैं, पिजनहोल सिद्धांत द्वारा, एक डुप्लिकेट होना चाहिए। हमें डुप्लिकेट ढूंढना है। यहां हमारा लक्ष्य O(n) समय और कॉन्स्टेंट स्पेस में कार्य करना है।

उदाहरण के लिए, यदि इनपुट है nums = [2,1,4,3,5,4], तो आउटपुट होगा 4।

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

चूंकि संख्याएं 1 से n तक हैं और लंबाई n+1 है, सभी तत्वों का योग अपेक्षित योग n*(n+1)/2 से घटाने पर डुप्लिकेट मिल जाता है।

• q = sum(nums) की गणना करें।
• n = len(nums)।
• v = (n - 1) * n // 2 (1 से n-1 तक का योग) की गणना करें।
• q - v लौटाएं।

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

def solve(nums):
    q = sum(nums)
    n = len(nums)
    v = (n - 1) * (n) // 2
    return q - v

nums = [2,1,4,3,5,4]
print(solve(nums))

इनपुट

[2,1,4,3,5,4]

आउटपुट

4