Majority element

[nishant3721]

Description

Divide and Conquer

DSA Problem

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

[nishant3721]

please assign this issue to me!

[tr1ppyb0y]

@nishant3721 I would like to submit the solution for this, here is my code in python

from typing import List, Any

class Solution:
    def __init__(self, arr: List[int]) -> None:
        self.arr = arr

    def find_majority_element(self) -> Any:
        neg_count, majority_ele = 0, -1
        for val in self.arr:
            if neg_count == 0:
                majority_ele = val
                neg_count += 1
            elif val == majority_ele:
                neg_count += 1
            else:
                neg_count -= 1

        n, count = len(arr), arr.count(majority_ele)
        if count > n // 2:
            return majority_ele
        return 'No majority element present'

if __name__ == "__main__":
    arr = tuple(map(int, input().split()))
    sol = Solution(arr)
    print(sol.find_majority_element())

in c++

#include <iostream>
#include <algorithm>
using namespace std;

class Solution {
public:
    Solution(int* arr, int n) : arr(arr), n(n) {}

    string find_majority_element() {
        int neg_count = 0, majority_ele = 0;
        for (int i = 0; i < n; i++)
            if (neg_count == 0) {
                majority_ele = arr[i];
                neg_count++;
            } else if (arr[i] == majority_ele)
                neg_count++;
              else
                neg_count--;

        int count = std::count(arr, arr + n, majority_ele);
        if (count > n / 2) {
            return to_string(majority_ele);
        }
        return "No majority element present";
    }

private:
    int* arr;
    int n;
};

int main() {
    int i = 0;
    cout << "Number of elements in array: ";
    cin >> i;
    int *arr = new int[i];
    for (int j = 0; j < i; j++)
        cin >> arr[j];

    Solution sol(arr, i);
    cout << sol.find_majority_element() << endl;
    return 0;
}

[tr1ppyb0y]

@nishant3721 I would like to submit the solution for this, here is my code in python

from typing import List, Any

class Solution:
    def __init__(self, arr: List[int]) -> None:
        self.arr = arr

    def find_majority_element(self) -> Any:
        neg_count, majority_ele = 0, -1
        for val in self.arr:
            if neg_count == 0:
                majority_ele = val
                neg_count += 1
            elif val == majority_ele:
                neg_count += 1
            else:
                neg_count -= 1

        n, count = len(arr), arr.count(majority_ele)
        if count > n // 2:
            return majority_ele
        return 'No majority element present'

if __name__ == "__main__":
    arr = tuple(map(int, input().split()))
    sol = Solution(arr)
    print(sol.find_majority_element())

in c++

#include <iostream>
#include <algorithm>
using namespace std;

class Solution {
public:
    Solution(int* arr, int n) : arr(arr), n(n) {}

    string find_majority_element() {
        int neg_count = 0, majority_ele = 0;
        for (int i = 0; i < n; i++)
            if (neg_count == 0) {
                majority_ele = arr[i];
                neg_count++;
            } else if (arr[i] == majority_ele)
                neg_count++;
              else
                neg_count--;

        int count = std::count(arr, arr + n, majority_ele);
        if (count > n / 2) {
            return to_string(majority_ele);
        }
        return "No majority element present";
    }

private:
    int* arr;
    int n;
};

int main() {
    int i = 0;
    cout << "Number of elements in array: ";
    cin >> i;
    int *arr = new int[i];
    for (int j = 0; j < i; j++)
        cin >> arr[j];

    Solution sol(arr, i);
    cout << sol.find_majority_element() << endl;
    return 0;
}

@iamdestinychild FYI.

[AYUSHMOHANTY10]

Assign this issue to me !! I will solve it using Python

[Divyamsirswal]

@nishant3721 This is cpp code

/ Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. /

#include<bits/stdc++.h>
using namespace std;

/*------------------------------------------------------------------------------*/
#define ll long long
#define vi vector<ll>
#define pi pair<ll,ll>
#define mp unordered_map<ll,ll>
#define f first
#define s second
#define pb push_back
#define mkp make_pair
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define out(i) cout<<i<<"\n"
#define line cout<<"\n"
#define all(x) x.begin(),x.end()
const ll N = 200100;
const ll mod = 1e9+7;
/*------------------------------------------------------------------------------*/

ll findMajorityElement(vi& temp,ll start,ll end){
  if(start == end){
    return temp[start];
  }
  ll mid = start + (end-start)/2;
  ll left = findMajorityElement(temp,start,mid);
  ll right = findMajorityElement(temp,mid+1,end);

  if(left == right){
    return left;
  }

  ll leftCnt=0;
  ll rightCnt=0;
  rep(i,start,end){
    if(temp[i]==left){
      leftCnt++;
    }else if(temp[i]==right){
      rightCnt++;
    }
  }
  return (leftCnt > rightCnt) ? left : right;

}

ll demo(vi& temp){
  return findMajorityElement(temp,0,temp.size()-1);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int num;
    cin>>num;

    vi temp(num);

    rep(i,0,num){
      cin>>temp[i];
    }

    ll result = demo(temp);

    cout<<result<<endl;

}