ধরুন আমাদের একটি অ্যারে আছে; প্রদত্ত সংখ্যা x সেই অ্যারের সংখ্যাগরিষ্ঠ উপাদান কিনা তা আমাদের পরীক্ষা করতে হবে। অ্যারে সাজানো হয়. একটি উপাদানকে সংখ্যাগরিষ্ঠ উপাদান বলা হয় যখন এটি অ্যারেতে n/2 বার প্রদর্শিত হয়। ধরুন একটি অ্যারে হল {1, 2, 3, 3, 3, 3, 6}, x =3, এখানে উত্তরটি সত্য কারণ 3 হল অ্যারের সংখ্যাগরিষ্ঠ উপাদান। চারটি 3s আছে। অ্যারের আকার 7, তাই আমরা 4> 7/2 দেখতে পাচ্ছি।
আমরা অ্যারেতে x এর উপস্থিতি গণনা করতে পারি, এবং সংখ্যাটি n/2-এর চেয়ে বেশি হলে উত্তরটি সত্য হবে, অন্যথায় মিথ্যা।
উদাহরণ (C++)
#include <iostream>
#include <stack>
using namespace std;
bool isMajorityElement(int arr[], int n, int x){
int freq = 0;
for(int i = 0; i<n; i++){
if(arr[i] == x )
freq++;
if(arr[i] > x)
break;
}
return (freq > n/2);
}
int main() {
int arr[] = {1, 2, 3, 3, 3, 3, 6};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 3;
if (isMajorityElement(arr, n, x))
cout << x << " is the majority element of the array";
else
cout << x << " is not the majority element of the array";
} ইনপুট
[1, 2, 3, 3, 3, 3, 6] 3
আউটপুট
3 is the majority element of the array
