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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Moore's Voting Algorithm on a given list

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

DSA Python

def majority_element(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

print(majority_element([2, 2, 1, 1, 1, 2, 2]))

A Error

B 1

C None

D 2

💡 Hint

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

The algorithm picks candidate 2 and confirms it as majority because it appears 4 times out of 7.

🧠 Conceptual

intermediate

Understanding the count variable in Moore's Voting Algorithm

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

A The number of times the current candidate has been seen minus the number of times other elements have been seen

B The total number of elements processed so far

C The index of the current candidate in the list

D The number of unique elements encountered

💡 Hint

Think about how the algorithm balances the candidate count.

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

❓ Predict Output

advanced

Output when no majority element exists

What will the following code output when run on a list with no majority element?

DSA Python

def majority_element(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

print(majority_element([1, 2, 3, 4]))

A 2

B 1

C 3

D 4

💡 Hint

Trace the algorithm step by step to see the final candidate.

The candidate ends as 3 after the last iteration, but it is not a true majority.

🔧 Debug

advanced

Identify the error in this Moore's Voting Algorithm implementation

What error will this code produce when run?

DSA Python

def majority_element(nums):
    count = 0
    candidate = None
    for num in nums:
        if count = 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

print(majority_element([3,3,4,2,4,4,2,4,4]))

A SyntaxError

B TypeError

C NameError

D No error, outputs 4

💡 Hint

Check the if condition syntax carefully.

The code uses '=' instead of '==' in the if condition, causing a SyntaxError.

🧠 Conceptual

expert

Why Moore's Voting Algorithm requires a second pass in some cases

Why might Moore's Voting Algorithm require a second pass over the list after finding a candidate?

A To sort the list for easier majority detection

B To verify that the candidate actually appears more than half the time

C To count the total number of unique elements

D To reset the candidate and count variables

💡 Hint

The algorithm assumes a majority element exists but does not confirm it.

The first pass finds a candidate, but the second pass confirms if it truly is the majority.

Practice

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

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:

• Confusing majority element with most frequent element
• Thinking it sorts the array
• Assuming it counts unique elements

2. Which of the following is the correct initialization step in Moore's Voting Algorithm in Python?

easy

A. count = 0; candidate = 0

B. count = 1; candidate = 0

C. count = None; candidate = 0

D. count = 0; candidate = None

Solution

1. Step 1: Recall initialization in Moore's Voting Algorithm

   We start with count = 0 and candidate = None to indicate no candidate chosen yet.

2. Step 2: Check other options for correctness

   Starting count at 1 or candidate at 0 without context is incorrect; None is used to indicate no candidate.

3. Final Answer:

   count = 0; candidate = None -> Option D

4. Quick Check:

   Initialize count=0 and candidate=None [OK]

Hint: Start count at 0 and candidate as None [OK]

Common Mistakes:

• Starting count at 1 instead of 0
• Assigning candidate to 0 prematurely
• Using None for count instead of candidate

3. What will be the output of the following code snippet?

def majority_element(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

print(majority_element([2,2,1,1,1,2,2]))

medium

A. 2

B. 1

C. None

D. Error

Solution

1. Step 1: Trace the candidate and count updates

   Start with count=0, candidate=None. Iterate: 2 (count=0->1, candidate=2), 2 (count=2), 1 (count=1), 1 (count=0), 1 (count=1, candidate=1), 2 (count=0), 2 (count=1, candidate=2).

2. Step 2: Final candidate after iteration

   The candidate ends as 2 after the loop finishes.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Majority element in [2,2,1,1,1,2,2] is 2 [OK]

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

Common Mistakes:

• Not updating candidate when count is zero
• Confusing candidate with last element
• Assuming candidate is None if count resets

4. Identify the bug in this Moore's Voting Algorithm implementation:

def majority_element(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        if num == candidate:
            count += 1
        else:
            count -= 1
    return candidate

print(majority_element([3,3,4]))

medium

A. Count increment/decrement logic is reversed

B. No bug, code works correctly

C. Candidate not updated when count is zero

D. Function does not handle empty list

Solution

1. Step 1: Analyze candidate update and count logic

   Candidate updates when count is zero. Count increments if current num equals candidate, else decrements.

2. Step 2: Test with input [3,3,4]

   Iteration: 3 (count=1, candidate=3), 3 (count=2), 4 (count=1). Returns candidate 3 correctly.

3. Final Answer:

   No bug, code works correctly -> Option B

4. Quick Check:

   Code correctly finds majority element [OK]

Hint: Check candidate update and count changes carefully [OK]

Common Mistakes:

• Thinking candidate is not updated when count is zero
• Confusing increment and decrement logic
• Ignoring empty list edge case

5. Given an array where no element appears more than half the time, what will Moore's Voting Algorithm return?
Example: [1,2,3,4]

hard

A. Error or exception

B. The element with highest frequency

C. None or incorrect candidate

D. The first element of the array

Solution

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

   The algorithm assumes a majority element exists (more than half the array). If none exists, it still returns a candidate but it may be incorrect.

2. Step 2: Apply to example [1,2,3,4]

   No element appears more than 2 times (half of 4). The algorithm returns a candidate but it is not a true majority.

3. Final Answer:

   None or incorrect candidate -> Option C

4. Quick Check:

   No majority means candidate may be wrong [OK]

Hint: Algorithm assumes majority exists; else candidate may be wrong [OK]

Common Mistakes:

• Assuming algorithm returns error if no majority
• Thinking it returns highest frequency element always
• Believing it returns first element by default