Boyer–Moore majority vote algorithm in C
Boyer-Moore majority vote algorithm
Boyer–Moore majority vote algorithm in C is one of the popular optimal algorithms which is used to find the majority element among the given elements of the array, that have more than N/ 2 occurrences. Boyer–Moore’s majority vote algorithm works perfectly fine for finding the majority element which takes 2 traversals over the given elements, which works in O(N) time complexity and O(1) space complexity.
Boyer-Moore Majority Vote Algorithm in C
The Boyer-Moore Majority Vote Algorithm is an efficient algorithm for finding the majority element in an array, which is an element that appears more than n/2 times, where n is the length of the array.
Note
The algorithm works in O(n) time complexity and O(1) space complexity, which makes it very efficient for large arrays.
Example:
Input: k = 6, arr = [ 1, 2, 5, 2, 2, 2 ] Output: Majority Element is 2
Algorithm :
- Take the size of the array and store it in variable n.
- Take n elements of the array from the user.
- Declare two variables one is maj_index and initialize it with 0, and one variable count with value 0.
- Run a loop from index 1 to n-1
- Check if a[i]==a[maj_index] then increase the value of count by 1, else decrease it by 1.
- If count becomes zero then set maj_index=i and count =1.
- Now create one function check that will check whether the maj_index value presents n/2 times or not.
- If it is present then return 1, otherwise 0(means no elements present more than n/2 times).
C code
#include<stdio.h>
int find_majority (int a[], int size)
{
int maj_index = 0, count = 1;
for (int i = 1; i < size; i++)
{
if (a[i] == a[maj_index])
count++;
else
count--;
if (count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}
int check_maj (int a[], int n, int k)
{
int count = 0;
for (int i = 0; i < n; i++) { if (a[i] == k) count++; } if (count > n / 2)
return 1;
else
return 0;
}
int main ()
{
int k;
int a[] = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
int n = sizeof (a) / sizeof (a[0]);
k = find_majority (a, n);
if (check_maj (a, n, k))
printf ("Majority element is %d", k);
else
printf ("No Majority element\n");
return 0;
}
Output:
Majority Element is 4
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Login/Signup to comment