Majority Element Moore's Voting Algorithm in DSA Go - 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 Go code that implements Moore's Voting Algorithm to find the majority element?

DSA Go

package main
import "fmt"
func majorityElement(nums []int) int {
    count := 0
    candidate := 0
    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}
func main() {
    arr := []int{2, 2, 1, 1, 1, 2, 2}
    fmt.Println(majorityElement(arr))
}

A 1

B 2

C 0

D Error

💡 Hint

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

The algorithm picks candidate 2 and counts its occurrences. Since 2 appears 4 times out of 7, it is the majority element.

🧠 Conceptual

intermediate

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 sum of all elements seen so far

B The total number of elements processed so far

C The index of the current candidate in the array

D The number of times the current candidate has been confirmed minus the times it was contradicted

💡 Hint

Think about how the algorithm balances candidate votes.

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

🔧 Debug

advanced

Identify the error in this Moore's Voting Algorithm implementation

What error will this Go code produce when run, and why?

DSA Go

package main
import "fmt"
func majorityElement(nums []int) int {
    count := 0
    candidate := 0
    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}
func main() {
    arr := []int{3, 3, 4}
    fmt.Println(majorityElement(arr))
}

A Output is 3

B Runtime panic due to nil pointer dereference

C Syntax error due to assignment in if condition

D Output is 4

💡 Hint

Check the if condition syntax carefully.

The line 'if count = 0' uses assignment '=' instead of comparison '==', causing a syntax error.

🚀 Application

advanced

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

You receive a stream of integers one by one. How can Moore's Voting Algorithm be adapted to find the majority element without storing the entire stream?

A Keep track of a candidate and count as elements arrive, updating them on the fly

B Store all elements and count frequencies after the stream ends

C Use a hash map to store counts for all elements in the stream

D Sort the stream elements as they arrive to find the middle element

💡 Hint

Moore's Voting Algorithm is designed for one-pass processing.

The algorithm maintains a candidate and count incrementally, so it works well for streams without storing all data.

❓ Predict Output

expert

Output of Moore's Voting Algorithm on array with no majority element

What is the output of this Go code using Moore's Voting Algorithm on an array with no majority element?

DSA Go

package main
import "fmt"
func majorityElement(nums []int) int {
    count := 0
    candidate := 0
    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}
func main() {
    arr := []int{1, 2, 3, 4, 5}
    fmt.Println(majorityElement(arr))
}

A 5

B 1

C 3

D No majority element found

💡 Hint

Moore's Voting Algorithm returns a candidate but does not guarantee majority.

The algorithm returns 5 as candidate after processing, but since no element appears more than half, it's not a true majority.

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 times

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

   It is designed to find the majority element, which is the element that appears more than half the times in the array.

2. Step 2: Compare with other options

   Sorting, finding smallest element, or counting unique elements are not the algorithm's purpose.

3. Final Answer:

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

4. Quick Check:

   Majority element = element appearing > n/2 times [OK]

Hint: Majority element appears more than half the array length [OK]

Common Mistakes:

• Confusing majority element with most frequent element
• Thinking it sorts the array
• Assuming it finds smallest or unique elements

2. Which of the following Go code snippets correctly initializes the variables needed for Moore's Voting Algorithm?

easy

A. count := 0; candidate := 0

B. var count int = 1; var candidate int = -1

C. count := 0; candidate := ''

D. var count string = '0'; var candidate int = 0

Solution

1. Step 1: Identify correct variable types and initialization

   Moore's Voting Algorithm uses an integer count starting at 0 and an integer candidate initialized to 0 or any valid integer.

2. Step 2: Check each option for type correctness

   count := 0; candidate := 0 uses count and candidate as integers with proper initialization. var count int = 1; var candidate int = -1 initializes count to 1 which is not standard start. count := 0; candidate := '' uses empty string for candidate which is wrong type. var count string = '0'; var candidate int = 0 uses string type for count which is incorrect.

3. Final Answer:

   count := 0; candidate := 0 -> Option A

4. Quick Check:

   Integer count and candidate initialized to 0 [OK]

Hint: Count starts at 0, candidate is integer zero [OK]

Common Mistakes:

• Using wrong data types for count or candidate
• Starting count at 1 instead of 0
• Initializing candidate with empty string

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

arr := []int{2, 2, 1, 1, 1, 2, 2}
count := 0
candidate := 0
for _, num := range arr {
  if count == 0 {
    candidate = num
  }
  if num == candidate {
    count++
  } else {
    count--
  }
}
fmt.Println(candidate)

medium

A. 1

B. 0

C. 2

D. 3

Solution

1. Step 1: Trace the loop to find candidate

   Start with count=0, candidate=0.
   Iteration 1: count=0, candidate=2, count=1
   Iteration 2: num=2 == candidate=2, count=2
   Iteration 3: num=1 != candidate=2, count=1
   Iteration 4: num=1 != candidate=2, count=0
   Iteration 5: count=0, candidate=1, count=1
   Iteration 6: num=2 != candidate=1, count=0
   Iteration 7: count=0, candidate=2, count=1

2. Step 2: Final candidate after loop

   The candidate after the loop ends is 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Majority element found = 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
• Miscounting increments and decrements

4. Identify the bug in this Go code implementing Moore's Voting Algorithm:

arr := []int{3, 3, 4, 2, 4, 4, 2, 4, 4}
count := 0
candidate := 0
for i := 0; i < len(arr); i++ {
  if count == 0 {
    candidate = arr[i]
  }
  if arr[i] == candidate {
    count--
  } else {
    count++
  }
}
fmt.Println(candidate)

medium

A. Candidate is not updated when count is zero

B. Candidate initialized incorrectly

C. Loop index goes out of range

D. Count increments and decrements are reversed

Solution

1. Step 1: Analyze count update logic

   The algorithm should increase count when current element equals candidate, and decrease count otherwise.

2. Step 2: Identify the bug in code

   Here, count is decreased when arr[i] == candidate and increased otherwise, which is reversed.

3. Final Answer:

   Count increments and decrements are reversed -> Option D

4. Quick Check:

   Correct count update: increment if equal, decrement if not [OK]

Hint: Increment count if equal, decrement if different [OK]

Common Mistakes:

• Swapping increment and decrement operations
• Not updating candidate when count is zero
• Incorrect loop bounds causing runtime errors

5. Given an array where no element appears more than half the time, how can Moore's Voting Algorithm be adapted to confirm the absence of a majority element?

hard

A. Return the candidate directly without verification

B. Run the algorithm to find a candidate, then verify its count exceeds half the array length

C. Sort the array and pick the middle element

D. Count all elements and pick the one with maximum frequency without verification

Solution

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

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

2. Step 2: Adaptation to confirm majority

   After finding candidate, count its occurrences in the array. If count > n/2, candidate is majority; else no majority element exists.

3. Final Answer:

   Run the algorithm to find a candidate, then verify its count exceeds half the array length -> Option B

4. Quick Check:

   Verify candidate count > n/2 to confirm majority [OK]

Hint: Verify candidate count after algorithm to confirm majority [OK]

Common Mistakes:

• Assuming candidate is always majority without verification
• Using sorting instead of Moore's Voting Algorithm
• Picking max frequency without checking majority condition