পাইথনের উপাদানগুলির একটি তালিকা থেকে সদৃশ আইটেম খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে n + 1 আকারের সংখ্যা বলা উপাদানগুলির একটি তালিকা রয়েছে, সেগুলি 1, 2, ..., n পরিসীমা থেকে নির্বাচন করা হয়েছে। আমরা জানি, pigeonhole নীতি দ্বারা, একটি সদৃশ হতে হবে. আমাদের ডুপ্লিকেট খুঁজে বের করতে হবে। এখানে আমাদের লক্ষ্য হল O(n) সময় এবং ধ্রুবক স্থানের মধ্যে টাস্ক খুঁজে বের করা।

সুতরাং, ইনপুট যদি সংখ্যার মত হয় =[2,1,4,3,5,4], তাহলে আউটপুট হবে 4

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

q :=সংখ্যায় উপস্থিত সমস্ত উপাদানের যোগফল
n :=সংখ্যার আকার
v :=((n - 1)*(n)/2)
এর ফ্লোর
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]