Majority Element Moore's Voting Algorithm in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Moore's Voting Algorithm on a given array

What is the output of the following C# code that implements Moore's Voting Algorithm to find the majority element?

DSA C#

using System;
class Program {
    static int FindMajorityElement(int[] nums) {
        int count = 0, candidate = -1;
        foreach (int num in nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
    static void Main() {
        int[] arr = {2, 2, 1, 1, 1, 2, 2};
        Console.WriteLine(FindMajorityElement(arr));
    }
}

A Throws an exception

B 2

C 0

D 1

💡 Hint

The majority element is the one that appears more than half the time in the array.

The algorithm picks candidate 2 and confirms it as majority because it appears 4 times out of 7, which is more than half.

❓ Predict Output

intermediate

Result when no majority element exists

What will the following C# code output when the input array has no majority element?

DSA C#

using System;
class Program {
    static int FindMajorityElement(int[] nums) {
        int count = 0, candidate = -1;
        foreach (int num in nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
    static void Main() {
        int[] arr = {1, 2, 3, 4, 5};
        Console.WriteLine(FindMajorityElement(arr));
    }
}

A 5

B 3

C -1

D 1

💡 Hint

The algorithm returns a candidate even if no majority exists.

The algorithm returns 5 as candidate but it is not a majority element because no element appears more than half the time.

🔧 Debug

advanced

Identify the bug in Moore's Voting Algorithm implementation

What error will the following C# code produce when run?

DSA C#

using System;
class Program {
    static int FindMajorityElement(int[] nums) {
        int count = 0, candidate = 0;
        foreach (int num in nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
    static void Main() {
        int[] arr = {2, 2, 1, 1, 1, 2, 2};
        Console.WriteLine(FindMajorityElement(arr));
    }
}

A Outputs 0

B RuntimeException

C Outputs 2

D SyntaxError

💡 Hint

Check the condition inside the if statement carefully.

The condition uses assignment (=) instead of comparison (==), causing the if body to never execute (condition always false after assignment), so candidate remains 0.

🧠 Conceptual

advanced

Understanding the count variable in Moore's Voting Algorithm

In Moore's Voting Algorithm, what does the 'count' variable represent during the iteration over the array?

A The index of the current candidate in the array

B The number of times the current candidate has appeared consecutively

C The difference between the count of the candidate and other elements seen so far

D The total number of elements processed so far

💡 Hint

Think about how count changes when you see the candidate or a different element.

Count increases when the current element matches the candidate and decreases otherwise, tracking the net support for the candidate.

🚀 Application

expert

Applying Moore's Voting Algorithm to find majority element in a stream

You receive a stream of integers one by one and want to find the majority element at the end using Moore's Voting Algorithm. Which approach correctly updates the candidate and count as each new number arrives?

A Increment count if new number differs from candidate; decrement count if equal; reset candidate when count is zero.

B Always increment count when a new number arrives; reset candidate only if count exceeds half the stream length.

C Set candidate to new number every time; increment count only if new number equals previous candidate.

D If count is zero, set candidate to new number and count to 1; else if new number equals candidate, increment count; else decrement count.

💡 Hint

Recall how Moore's Voting Algorithm updates candidate and count during iteration.

Option D correctly describes the update rules of Moore's Voting Algorithm for streaming data.

Practice

1. What is the main purpose of Moore's Voting Algorithm in an array of integers?

easy

A. To find the element that appears more than half the time

B. To sort the array in ascending order

C. To find the smallest element in the array

D. To count the total number of unique elements

Solution

1. Step 1: Understand the problem Moore's Voting Algorithm solves

   The algorithm is designed to find the majority element, which is the element that appears more than half the time in the array.

2. Step 2: Compare with other options

   Sorting, finding smallest element, or counting unique elements are not the goals of this algorithm.

3. Final Answer:

   To find the element that appears more than half the time -> Option A

4. Quick Check:

   Majority element = element with >50% frequency [OK]

Hint: Majority element appears more than half times [OK]

Common Mistakes:

• Thinking it sorts the array
• Confusing majority with most frequent element without >50%
• Assuming it finds smallest or unique counts

2. Which of the following is the correct way to initialize the candidate and count variables in C# for Moore's Voting Algorithm?

easy

A. int candidate = -1; int count = 0;

B. int candidate; int count = 1;

C. int candidate = 0; int count = 0;

D. int candidate = 0; int count = 1;

Solution

1. Step 1: Understand initialization requirements

   Candidate should start with a default value (like 0) and count should start at 0 before processing the array.

2. Step 2: Check each option

   int candidate = 0; int count = 0; initializes candidate to 0 and count to 0, which is standard. int candidate; int count = 1; leaves candidate uninitialized. int candidate = -1; int count = 0; uses -1 which may be valid but less common. int candidate = 0; int count = 1; starts count at 1 which is incorrect before any element is processed.

3. Final Answer:

   int candidate = 0; int count = 0; -> Option C

4. Quick Check:

   Initialize candidate=0 and count=0 before loop [OK]

Hint: Start count at zero before scanning array [OK]

Common Mistakes:

• Leaving candidate uninitialized
• Starting count at 1 before processing
• Using invalid default candidate values

3. What will be the output of the following C# code snippet using Moore's Voting Algorithm?

int[] nums = {2, 2, 1, 1, 1, 2, 2};
int candidate = 0, count = 0;
foreach (int num in nums) {
  if (count == 0) candidate = num;
  count += (num == candidate) ? 1 : -1;
}
Console.WriteLine(candidate);

medium

A. 1

B. 2

C. 0

D. Error

Solution

1. Step 1: Trace the candidate and count updates

   Start with candidate=0, count=0. Iterate nums:
   - num=2: count=0, candidate=2, count=1
   - num=2: same candidate, count=2
   - num=1: different, count=1
   - num=1: different, count=0
   - num=1: count=0, candidate=1, count=1
   - num=2: different, count=0
   - num=2: count=0, candidate=2, count=1

2. Step 2: Final candidate after loop

   The final candidate is 2 after processing all elements.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Final candidate = 2 [OK]

Hint: Track count changes; candidate updates when count hits zero [OK]

Common Mistakes:

• Not updating candidate when count is zero
• Confusing candidate with last element
• Ignoring count increments and decrements

4. Identify the error in the following C# implementation of Moore's Voting Algorithm:

int[] nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};
int candidate = 0, count = 0;
foreach (int num in nums) {
  if (count == 0) candidate = num;
  if (num == candidate) count++;
  else count++;
}
Console.WriteLine(candidate);

medium

A. Count is incremented in both if and else, should decrement in else

B. Candidate is not updated when count is zero

C. Candidate should be initialized to -1

D. The array nums is empty

Solution

1. Step 1: Analyze count updates in loop

   Count is incremented in both if and else branches, so count never decreases. This breaks the algorithm logic.

2. Step 2: Correct the else branch

   In Moore's Voting Algorithm, count should decrement when current number is not the candidate.

3. Final Answer:

   Count is incremented in both if and else, should decrement in else -> Option A

4. Quick Check:

   Count must decrease when num != candidate [OK]

Hint: Count decreases when element differs from candidate [OK]

Common Mistakes:

• Incrementing count in else instead of decrementing
• Not updating candidate when count is zero
• Assuming candidate initialization causes error

5. Given an array int[] nums = {1, 2, 3, 2, 2, 2, 5, 2, 2}, how can you verify after Moore's Voting Algorithm that the candidate is actually the majority element?

hard

A. Sort the array and pick the middle element

B. Assume candidate is majority without verification

C. Check if candidate is the first element in the array

D. Count the occurrences of candidate in the array and check if it is more than half the array length

Solution

1. Step 1: Understand Moore's Voting Algorithm limitation

   The algorithm finds a candidate but does not guarantee it is majority if none exists.

2. Step 2: Verify candidate by counting occurrences

   Count how many times candidate appears and compare with half the array length to confirm majority.

3. Final Answer:

   Count the occurrences of candidate in the array and check if it is more than half the array length -> Option D

4. Quick Check:

   Verify candidate count > n/2 after algorithm [OK]

Hint: Always verify candidate count > half array length [OK]

Common Mistakes:

• Skipping verification step
• Assuming candidate is always majority
• Using sorting instead of counting