FIND MAJORITY ELEMENT IN AN ARRAY

Hi,friends this is very famous problem for interview purpose.

Question:What is majority element?
Ans:a element that appear more than (n/2)times in an array of size (n).

example: Arr:3 3 4 2 4 4 2 4 4
         Here n=9
         So n/2=4
         so majority element is a element that appear more than 4
         Here majority element is : 4(bcoz its count is 5).

 Simple Brute force approach is given below:
 Time complexity:o(n^2)
 Space complexity:o(1)

 If u have any doubt plz comment below:

 

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin >> n;

 int arr[n];
 cout << "Enter the elements of array:\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 for(i=0;i<n;i++){
  int count =0;
  for(j=0;j<n;j++){
   if(arr[i]==arr[j]){
    count++;
   }
  }
  if(count>(n/2)){
   cout << "majority element is:" << arr[i] ;
   break; 
  }
 }
 return 0;
}

Hi guys this is optimization for the majority element problem 
Time Complexity:o(n)
Space Complexity:o(1)

This code is based on the moore's voting algorithm:

Concept:
>step1:first of all we are simply taking 1st element as majority element and also one variable which shows how many time that element hash occured
>till now.
>step2:Now we are comparing array element with majority element if they are same then increse the count variable by 1
->else decrease count variable by 1
>step3:Now check if count is 0 then update maj_element and make its count 1.

If u guys still have doubt plz comment below

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin >> n;

 int arr[n];
 cout << "Enter the elements of array:\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 int maj_ele_index=0;
 int count=1;

 for(i=1;i<n;i++){
  if(arr[maj_ele_index]==arr[i]){
   count++;
  }
  else{
   count--;
   if(count==0){
    maj_ele_index=i;
    count=1;
   }
  }
 }

 //find the occurence of maj_element
 count=0;
 for(i=0;i<n;i++){
  if(arr[i]==arr[maj_ele_index]){
   count++;
  }
 }

 if(count>(n/2)){
  cout << "majority Element is:\n" << arr[maj_ele_index];
 }
 else{
  cout << "There is no element which occur more than n/2";
 }
 return 0;
}