পাইথনে লিস্ট থেকে ডুপ্লিকেট এলিমেন্ট বের করার প্রোগ্রাম (O(n) টাইম, O(1) স্পেস)

একটি লিস্ট nums (আকার n+1) দেওয়া আছে, এলিমেন্ট ১ থেকে n পর্যন্ত। পিজনহোল প্রিন্সিপল অনুযায়ী অবশ্যই একটি ডুপ্লিকেট থাকবে। O(n) টাইম এবং কনস্ট্যান্ট স্পেসে সেটি বের করুন।

উদাহরণ

nums = [2,1,4,3,5,4] → আউটপুট: 4

এলগরিদম (গাণিতিক ফর্মুলা)

1. q := sum(nums)
2. n := len(nums)
3. v := (n-1)*n//2 (১ থেকে n-1 পর্যন্ত যোগফল)
4. রিটার্ন 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))  # আউটপুট: 4

ইনপুট / আউটপুট

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