পাইথনে পেয়ার সম চেক করার ডেটা স্ট্রাকচার তৈরি করা (অন-দ-ফ্লাই কোয়েরি)

একটি ডেটা স্ট্রাকচার ডিজাইন করুন যাতে দুটি মেথড থাকে: add(val) - ভ্যালু যোগ করা, find(val) - কোনো দুটি উপাদানের যোগফল val কিনা চেক করা। প্রতি কোয়েরিতে লিনিয়ার সার্চ না করে অন-দ-ফ্লাই আন্সার দিতে হবে।

ইনপুট উদাহরণ

obj.add(6), obj.add(14), obj.add(3), obj.add(8), obj.add(11), obj.add(15)
obj.find(9)  → True (6+3)
obj.find(11) → True (3+8)
obj.find(15) → False

অ্যালগরিদম

1. nums সেট: সব উনিক ভ্যালু।
2. multiple সেট: যেসব ভ্যালু একাধিকবার অ্যাড হয়েছে।
3. find(val)-এ: প্রতিটি n in nums এর জন্য চেক করুন val-n in nums (যদি n != val-n) অথবা n in multiple (যদি n == val-n)।

পাইথন কোড

class PairSumChecker:
    def __init__(self):
        self.nums = set()
        self.multiple = set()
    
    def add(self, val):
        if val in self.nums:
            self.multiple.add(val)
        else:
            self.nums.add(val)
    
    def find(self, val):
        for n in self.nums:
            if n + n == val:
                return n in self.multiple
            elif val - n in self.nums:
                return True
        return False

# টেস্ট
obj = PairSumChecker()
obj.add(6); obj.add(14); obj.add(3); obj.add(8); obj.add(11); obj.add(15)
print(obj.find(9))   # True
print(obj.find(11))  # True
print(obj.find(15))  # False

ব্যাখ্যা

add: O(1)। find: O(u) (u = উনিক নম্বরের সংখ্যা)। স্পেস: O(u)। ডুপ্লিকেট হ্যান্ডলিং এর জন্য multiple সেট।