forked from DhanushNehru/Hacktoberfest2025
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMooreVotingAlgorithm.java
More file actions
40 lines (38 loc) · 1 KB
/
MooreVotingAlgorithm.java
File metadata and controls
40 lines (38 loc) · 1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
The Moore's Voting Algorithm is an efficient algorithm that finds the majority element in an array (an element that appears more than n/2 times)
with O(n) time complexity and O(1) space complexity.
*/
public class MooreVotingAlgorithm {
public static int majorityElement(int arr[]){
int c=0;
int n=arr.length;
int ele=0;
for(int i=0;i<n;i++){
if(c==0){
c=1;
ele=arr[i];
}
else if(ele==arr[i]){
c++;
}
else{
c--;
}
}
int c1=0;
for(int i=0;i<n;i++){
if(arr[i]==ele){
c1++;
}
}
if(c1>n/2){
return ele;
}
return -1;
}
public static void main(String args[]){
int arr[]={1,1,2,5,2,2,2,2};
int ans=majorityElement(arr);
System.out.println("Majority Element in the array with occurance more than n/2 times : "+ans);
}
}