পাইথনে মেজোরিটি এলিমেন্ট (Majority Element) বের করুন

সমস্যা বিবরণ

একটি ইন্টিজার অ্যারে দেওয়া আছে। মেজোরিটি এলিমেন্ট হলো সেই এলিমেন্ট যা অ্যারেতে n/2 এর চেয়ে বেশি বার আসে (যেখানে n = অ্যারের সাইজ)। এমন এলিমেন্ট খুঁজে বের করা।

উদাহরণ

• ইনপুট-১: N=8, A=[1,2,4,3,3,1,1,5] → আউটপুট: ১ (৩ বার, n/2=4, তাই মেজোরিটি নয়? উদাহরণে বুলে ১ বলা হয়েছে, সম্ভবত "most frequent" अभिप্রาย।)
• ইনপুট-২: N=6, A=[1,5,4,4,1,1] → আউটপুট: ১ (৩ বার, n/2=3, স্ট্রিক্টলি >3 হলে মেজোরিটি নয়, কিন্তু উদাহরণে ১)।

স্পষ্টীকরণ: সাধারণত "Majority Element" মানে > n/2 বার। কিন্তু উদাহরণগুলো "Most Frequent Element" (Mode) বোঝাচ্ছে। নিচের কোডে দুটি ভার্সন দেওয়া হলো।

সমাধান ১: হ্যাশ ম্যাপ (ডিকশনারি) দিয়ে ফ্রিকোয়েন্সি কাউন্ট (O(n) টাইম, O(n) স্পেস)

def checkMajorityElement(arr, N):
    mp = {}
    for i in range(N):
        if arr[i] in mp:
            mp[arr[i]] += 1
        else:
            mp[arr[i]] = 1
    
    # স্ট্রিক্ট মেজোরিটি (> N/2)
    for key in mp:
        if mp[key] > N / 2:
            return key
    return -1

# টেস্ট
arr = [2, 1, 1, 2, 2, 2]
N = 6
ans = checkMajorityElement(arr, N)
if ans != -1:
    print(f"Majority Element (> n/2): {ans}")
else:
    print("কোনো মেজোরিটি এলিমেন্ট নেই (> n/2)")

# Most Frequent Element (Mode)
from collections import Counter
most_common = Counter(arr).most_common(1)[0][0]
print(f"Most Frequent Element: {most_common}")

সমাধান ২: বয়ার-মур মেজোরিটি ভোট অ্যালগরিদম (O(n) টাইম, O(1) স্পেস)

শুধু মেজোরিটি এলিমেন্ট (> n/2) খুঁজতে চাইলে এটি সেরা।

def majorityElement(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    # ভেরিফিকেশন (ঐচ্ছিক)
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return -1

print(majorityElement([2,1,1,2,2,2]))  # 2

আউটপুট

Majority Element (> n/2): 2
Most Frequent Element: 2

নোট: উদাহরণে দেওয়া ইনপুট-১ এ ১ মাত্র ৩ বার এসে (n=8, n/2=4), স্ট্রিক্ট মেজোরিটি নয়। কোডটি আপনার ডেফিনিশন অনুযায়ী বেছে নিন।