Majority Element Moore's Voting Algorithm in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the candidate variable.

DSA C

int findMajorityElement(int arr[], int n) {
    int count = 0;
    int candidate = [1];
    for (int i = 0; i < n; i++) {
        if (count == 0) {
            candidate = arr[i];
            count = 1;
        } else if (arr[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

Drag options to blanks, or click blank then click option'

A0

Barr[0]

C-1

Darr[1]

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing candidate to 0 or -1 which may not be in the array.

Not initializing candidate before the loop.

The candidate is initially set to the first element of the array to start the voting process.

2fill in blank

medium

Complete the code to update the count when the current element matches the candidate.

DSA C

if (arr[i] == candidate) {
    [1];
}

Drag options to blanks, or click blank then click option'

Acount = 0

Bcount = 1

Ccount++

Dcount--

Attempts:

3 left

💡 Hint

Common Mistakes

Decreasing count instead of increasing it.

Resetting count to 0 or 1 incorrectly.

When the current element matches the candidate, increase the count by one.

3fill in blank

hard

Fix the error in the condition to reset the candidate and count.

DSA C

if (count == [1]) {
    candidate = arr[i];
    count = 1;
}

Drag options to blanks, or click blank then click option'

A0

B1

C-1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Resetting candidate when count is 1 instead of 0.

Using negative values in the condition.

The candidate and count reset when count reaches zero, not one.

4fill in blank

hard

Fill both blanks to complete the verification loop that confirms the majority element.

DSA C

int verifyCount = 0;
for (int i = 0; i < n; i++) {
    if (arr[i] [1] candidate) {
        verifyCount [2];
    }
}
if (verifyCount > n / 2) {
    return candidate;
} else {
    return -1;
}

Drag options to blanks, or click blank then click option'

A==

B!=

C++

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' instead of '==' in the condition.

Decrementing verifyCount instead of incrementing.

We check if each element equals the candidate and increment verifyCount if true.

5fill in blank

hard

Fill all three blanks to complete the main function that tests the majority element function.

DSA C

#include <stdio.h>

int findMajorityElement(int arr[], int n);

int main() {
    int arr[] = {2, 2, 1, 1, 1, 2, 2};
    int n = [1];
    int result = findMajorityElement(arr, [2]);
    if (result != [3]) {
        printf("Majority element is %d\n", result);
    } else {
        printf("No majority element found\n");
    }
    return 0;
}

Drag options to blanks, or click blank then click option'

A7

Barr

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Passing wrong array length.

Using 0 instead of -1 for no majority element.

The array length is 7, passed twice, and -1 indicates no majority element.

Practice

1. What is the main purpose of Moore's Voting Algorithm in arrays?

easy

A. To sort the array in ascending order

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

C. To find the smallest element in the array

D. To reverse the array 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 time in the array.

2. Step 2: Compare other options

   Sorting, finding smallest, or reversing are unrelated to majority element detection.

3. Final Answer:

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

4. Quick Check:

   Majority element = element with > n/2 occurrences [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 finds smallest or largest element

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

easy

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

B. int count = 1, candidate = 0;

C. int candidate = 0, count = 0;

D. int candidate = -1, count = 1;

Solution

1. Step 1: Identify correct variable initialization

   Moore's Voting Algorithm starts with count = 0 and candidate = -1 (or any invalid index) to indicate no candidate chosen yet.

2. Step 2: Check other options

   Other options start count or candidate incorrectly, which can cause logic errors.

3. Final Answer:

   int count = 0, candidate = -1; -> Option A

4. Quick Check:

   Start with no candidate and zero count [OK]

Hint: Initialize count=0 and candidate invalid (-1) [OK]

Common Mistakes:

• Starting count at 1 instead of 0
• Assigning candidate to 0 prematurely
• Swapping order of variables

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

int arr[] = {2, 2, 1, 1, 1, 2, 2};
int n = 7;
int count = 0, candidate = -1;
for (int i = 0; i < n; i++) {
  if (count == 0) {
    candidate = arr[i];
  }
  if (arr[i] == candidate) {
    count++;
  } else {
    count--;
  }
}
printf("%d", candidate);

medium

A. 1

B. 0

C. 2

D. No majority element

Solution

1. Step 1: Trace the candidate and count updates

   Start count=0, candidate=-1
   i=0: count=0, candidate=2, count=1
   i=1: arr[i]=2 == candidate=2, count=2
   i=2: arr[i]=1 != candidate=2, count=1
   i=3: arr[i]=1 != candidate=2, count=0
   i=4: count=0, candidate=1, count=1
   i=5: arr[i]=2 != candidate=1, count=0
   i=6: count=0, candidate=2, count=1

2. Step 2: Final candidate after loop

   Candidate is 2 after loop ends.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Majority element found = 2 [OK]

Hint: Track count and candidate changes stepwise [OK]

Common Mistakes:

• Not resetting candidate when count hits zero
• Confusing candidate with last element
• Ignoring count decrement on mismatch

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

int count = 0, candidate = -1;
for (int i = 0; i < n; i++) {
  if (count == 0) {
    candidate = arr[i];
  }
  if (arr[i] != candidate) {
    count++;
  } else {
    count--;
  }
}

medium

A. Candidate initialized incorrectly

B. Candidate is not updated when count is zero

C. Loop does not run for all elements

D. Count increment and decrement conditions are reversed

Solution

1. Step 1: Check count update logic

   Correct logic: increment count if element equals candidate, decrement otherwise.
   Given code increments count when arr[i] != candidate, which is wrong.

2. Step 2: Confirm candidate update and loop correctness

   Candidate updates correctly when count == 0.
   Loop runs correctly for all elements.
   Candidate initialization is valid.

3. Final Answer:

   Count increment and decrement conditions are reversed -> Option D

4. Quick Check:

   Increment on match, decrement on mismatch [OK]

Hint: Increment count on match, decrement on mismatch [OK]

Common Mistakes:

• Swapping increment and decrement conditions
• Not updating candidate when count is zero
• Incorrect loop bounds

5. Given an array int arr[] = {3, 3, 4, 2, 4, 4, 2, 4, 4}, how can you verify if the candidate found by Moore's Voting Algorithm is actually a majority element?

hard

A. Count occurrences of candidate and check if it is more than n/2

B. Check if candidate is at the first position of the array

C. Verify if candidate is the maximum element in the array

D. No verification needed; candidate is always majority

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 in array.
   If count > n/2, candidate is majority; else no majority element.

3. Final Answer:

   Count occurrences of candidate and check if it is more than n/2 -> Option A

4. Quick Check:

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

Hint: Always verify candidate count > n/2 after algorithm [OK]

Common Mistakes:

• Assuming candidate is always majority without check
• Checking candidate position instead of count
• Confusing majority with max element