Majority Element Moore's Voting Algorithm in DSA Go - Build from Scratch

Majority Element Moore's Voting Algorithm

📖 Scenario: Imagine you are analyzing votes in a small town election. You want to find the candidate who got more than half of the votes. This candidate is called the majority element.

🎯 Goal: Build a Go program that uses Moore's Voting Algorithm to find the majority element in a list of votes.

📋 What You'll Learn

Create a slice of integers called votes with the exact values: 2, 2, 1, 1, 1, 2, 2

Create an integer variable called count and set it to 0

Use a for loop with variable vote to iterate over votes and implement Moore's Voting Algorithm to find the majority element stored in candidate

Print the value of candidate as the majority element

💡 Why This Matters

🌍 Real World

Finding the majority element helps in elections, surveys, and decision-making processes where one option dominates.

💼 Career

Understanding Moore's Voting Algorithm is useful for software engineers working on data analysis, voting systems, and algorithms optimization.

1

Create the votes slice

Create a slice of integers called votes with these exact values: 2, 2, 1, 1, 1, 2, 2

DSA Go

# Your code here

Hint

Use votes := []int{2, 2, 1, 1, 1, 2, 2} to create the slice.

2

Initialize count and candidate

Create an integer variable called count and set it to 0. Also create an integer variable called candidate and set it to 0.

DSA Go

package main

func main() {
    votes := []int{2, 2, 1, 1, 1, 2, 2}
    // Your code here
}

Hint

Use count := 0 and candidate := 0 to initialize.

3

Implement Moore's Voting Algorithm

Use a for loop with variable vote to iterate over votes. Inside the loop, if count is 0, set candidate to vote. Then, if vote equals candidate, increase count by 1, else decrease count by 1.

DSA Go

package main

func main() {
    votes := []int{2, 2, 1, 1, 1, 2, 2}
    count := 0
    candidate := 0
    // Your code here
}

Hint

Use for _, vote := range votes to loop. Update candidate and count as described.

4

Print the majority element

Print the value of candidate as the majority element using fmt.Println.

DSA Go

package main

import "fmt"

func main() {
    votes := []int{2, 2, 1, 1, 1, 2, 2}
    count := 0
    candidate := 0

    for _, vote := range votes {
        if count == 0 {
            candidate = vote
        }
        if vote == candidate {
            count++
        } else {
            count--
        }
    }
    // Your code here
}

Hint

Use fmt.Println(candidate) to print the majority element.

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