majorityDAC.cpp

#include <iostream>
using namespace std;

class MajorityElement {
public:
    int countOccurrences(int arr[], int n, int num) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == num) count++;
        }
        return count;
    }

    int findMajority(int arr[], int left, int right) {
        if (left == right) return arr[left]; // Base case: single element

        int mid = (left + right) / 2;
        int leftMajor = findMajority(arr, left, mid);
        int rightMajor = findMajority(arr, mid + 1, right);

        if (leftMajor == rightMajor) return leftMajor;

        int leftCount = countOccurrences(arr + left, right - left + 1, leftMajor);
        int rightCount = countOccurrences(arr + left, right - left + 1, rightMajor);

        return (leftCount > (right - left + 1) / 2) ? leftMajor : 
               (rightCount > (right - left + 1) / 2) ? rightMajor : -1;
    }

    int getMajorityElement(int arr[], int n) {
        return findMajority(arr, 0, n - 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;
}