search

TheAlgorithms / C-Plus-Plus

Collection of various algorithms in mathematics, machine learning, computer science and physics implemented in C++ for educational purposes.
https://thealgorithms.github.io/C-Plus-Plus
MIT License
30.79k stars 7.29k forks source link

[FEATURE] Moore Voting Algorithm #2830

Open SuprHUlk opened 1 month ago

SuprHUlk commented 1 month ago

Detailed description

Detailed description: Problem Statement: The Moore Voting Algorithm is an efficient way to find the majority element in an array. A majority element is defined as an element that appears more than n/2 times in the array, where n is the length of the array. The algorithm works in two phases:

Candidate Selection: Traverse the array and choose a candidate for the majority element by maintaining a count. When the count reaches zero, a new candidate is selected.

Verification: Verify that the candidate is indeed the majority element by counting its occurrences in a second pass through the array.

The algorithm has a time complexity of O(n) and a space complexity of O(1).

Context

This algorithm is important in scenarios where the majority element needs to be identified efficiently, such as in voting systems or stream processing applications. The typical brute-force or sorting approaches have higher time complexities, whereas Moore Voting Algorithm is optimal for this type of problem.

This change benefits users who are working on algorithms that involve large datasets, providing them with a more efficient solution for finding a dominant or majority element in a list or array.

Possible implementation

Possible implementation: The Moore Voting Algorithm can be implemented with the following steps:

  1. Initialize a variable candidate to store the current candidate and a variable count to track the candidate’s occurrences.

  2. Traverse the array, adjusting the candidate and count.

  3. Verify by making a second pass through the array to check if the selected candidate appears more than n / 2 times.

Test Case Example:

Input: [3, 3, 4, 2, 4, 4, 2, 4, 4]

Expected Output: Majority Element: 4

Additional information

No response

realstealthninja commented 1 month ago

feel free to raise a pr and link it here

SuprHUlk commented 1 month ago

sure

Aditya-jain-0 commented 1 month ago

Hey , Can you assign this to me

SuprHUlk commented 1 month ago

@realstealthninja I have implemented the algorithm and have raised a PR . Review: PR -> #2847.

Looking forward to your feedback. Thank you for the opportunity to contribute!

Divyansh-jain2 commented 1 month ago

assign this to me

vaishnavi878 commented 1 month ago

/assign