একটি ইন্টিজার অ্যারে দেওয়া থাকলে, সেই এলিমেন্টটি খুঁজে বের করতে হবে যা অ্যারেতে আরও বেশি বার (n/2 এর চেয়ে বেশি) উপস্থিত আছে।
ইনপুট-১: N = 8, A[] = {1,2,4,3,3,1,1,5} → আউটপুট: 1 (কারণ ১ তিনবার এসেছে, যা ৮/২=৪ এর চেয়ে কম? Wait, majority means > n/2. Here n=8, n/2=4, 1 appears 3 times, not majority. The example says output 1 but explanation says most appearing number is 1. Actually majority element is defined as element appearing > n/2 times. In example 1, 1 appears 3 times, not >4. So example is flawed. But we follow the typical definition: element appearing > n/2 times. The code uses HashMap and checks > N/2. So we'll correct explanation.)
সঠিক উদাহরণ: N=6, A[]={2,1,1,2,2,2} → আউটপুট: 2 (২ চারবার এসেছে, ৬/২=৩ এর চেয়ে বেশি)।
সমাধানের পদ্ধতি
লিনিয়ার টাইম O(n) এবং লিনিয়ার স্পেস O(n) এ এই সমস্যা সমাধান করতে HashMap ব্যবহার করা হয়।
- অ্যারের সাইজ N ইনপুট নিন।
- একটি HashMap তৈরি করুন যেখানে Key হবে এলিমেন্ট এবং Value হবে তার ফ্রিকোয়েন্সি।
- অ্যারেটি ট্রাভার্স করে ফ্রিকোয়েন্সি আপডেট করুন।
- Map-এ ইটারেট করে যেই এলিমেন্টের ফ্রিকোয়েন্সি N/2 এর চেয়ে বেশি, সেটি রিটার্ন করুন। না পাওয়া গেলে -1 রিটার্ন করুন।
জাভা কোড উদাহরণ
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
class MajorityElement {
public static int findMajority(int arr[], int N) {
Map freqMap = new HashMap<>();
for (int i = 0; i < N; i++) {
freqMap.put(arr[i], freqMap.getOrDefault(arr[i], 0) + 1);
}
for (Map.Entry entry : freqMap.entrySet()) {
if (entry.getValue() > N / 2)
return entry.getKey();
}
return -1;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("অ্যারের সাইজ লিখুন:");
int N = sc.nextInt();
int arr[] = new int[N];
System.out.println("অ্যারের এলিমেন্টগুলো লিখুন:");
for (int i = 0; i < N; i++)
arr[i] = sc.nextInt();
int ans = findMajority(arr, N);
if (ans != -1)
System.out.println("Majority Element: " + ans);
else
System.out.println("Majority element নেই");
}
}
আউটপুট
অ্যারের সাইজ লিখুন: 6 অ্যারের এলিমেন্টগুলো লিখুন: 2 1 1 2 2 2 Majority Element: 2
