majoritynormal.cpp

#include <iostream>
using namespace std;

class MajorityElement {
public:
    int findCandidate(int arr[], int n) {
        int candidate = arr[0], count = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] == candidate) 
                count++;
            else 
                count--;

            if (count == 0) {
                candidate = arr[i];
                count = 1;
            }
        }
        return candidate;
    }

    bool isMajority(int arr[], int n, int candidate) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == candidate) count++;
        }
        return count > n / 2;
    }

    int getMajorityElement(int arr[], int n) {
        int candidate = findCandidate(arr, n);
        return isMajority(arr, n, candidate) ? candidate : -1;
    }
};

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;

    int* arr = new int[n];
    cout << "Enter elements: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    MajorityElement obj;
    int result = obj.getMajorityElement(arr, n);

    if (result != -1)
        cout << "Majority Element: " << result << endl;
    else
        cout << "No Majority Element found" << endl;

    delete[] arr;
    return 0;
}