Challenge - 5 Problems
Moore's Voting Algorithm Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Moore's Voting Algorithm on a given array
What is the output of the following Rust code that implements Moore's Voting Algorithm to find the majority element?
DSA Rust
fn majority_element(nums: &[i32]) -> i32 {
let mut count = 0;
let mut candidate = 0;
for &num in nums {
if count == 0 {
candidate = num;
}
if num == candidate {
count += 1;
} else {
count -= 1;
}
}
candidate
}
fn main() {
let arr = [2, 2, 1, 1, 1, 2, 2];
println!("{}", majority_element(&arr));
}Attempts:
2 left
💡 Hint
The majority element appears more than half the time in the array.
✗ Incorrect
The algorithm keeps track of a candidate and a count. It increments count when the current number matches the candidate and decrements otherwise. When count reaches zero, it picks a new candidate. The final candidate is the majority element.
🧠 Conceptual
intermediate1:30remaining
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?
Attempts:
2 left
💡 Hint
Think about how count changes when the current number matches or differs from the candidate.
✗ Incorrect
Count increases when the current element matches the candidate and decreases otherwise. It represents the net support for the candidate.
❓ Predict Output
advanced2:00remaining
Output when no majority element exists
What is the output of the following Rust code using Moore's Voting Algorithm on an array with no majority element?
DSA Rust
fn majority_element(nums: &[i32]) -> i32 {
let mut count = 0;
let mut candidate = 0;
for &num in nums {
if count == 0 {
candidate = num;
}
if num == candidate {
count += 1;
} else {
count -= 1;
}
}
candidate
}
fn main() {
let arr = [1, 2, 3, 4, 5, 6];
println!("{}", majority_element(&arr));
}Attempts:
2 left
💡 Hint
The algorithm returns a candidate even if no majority exists.
✗ Incorrect
The algorithm returns the last candidate selected, which is 5 in this case, but it does not guarantee it is a majority element without verification.
🔧 Debug
advanced2:00remaining
Identify the error in this Moore's Voting Algorithm implementation
What error will this Rust code produce when trying to find the majority element?
DSA Rust
fn majority_element(nums: &[i32]) -> i32 {
let mut count = 0;
let mut candidate = None;
for &num in nums {
if count == 0 {
candidate = Some(num);
}
if num == candidate {
count += 1;
} else {
count -= 1;
}
}
candidate.unwrap()
}
fn main() {
let arr = [2, 2, 1, 1, 1, 2, 2];
println!("{}", majority_element(&arr));
}Attempts:
2 left
💡 Hint
Check the comparison between num and candidate.
✗ Incorrect
candidate is an Option, but the code compares it directly with i32, causing a type mismatch error.
🚀 Application
expert2:30remaining
Number of times count changes in Moore's Voting Algorithm
Given the array [1, 2, 2, 3, 2, 1, 2, 2], how many times does the 'count' variable change its value during the execution of Moore's Voting Algorithm?
DSA Rust
fn count_changes(nums: &[i32]) -> usize {
let mut count = 0;
let mut candidate = 0;
let mut changes = 0;
for &num in nums {
let old_count = count;
if count == 0 {
candidate = num;
}
if num == candidate {
count += 1;
} else {
count -= 1;
}
if count != old_count {
changes += 1;
}
}
changes
}
fn main() {
let arr = [1, 2, 2, 3, 2, 1, 2, 2];
println!("{}", count_changes(&arr));
}Attempts:
2 left
💡 Hint
Count every increment or decrement of the count variable.
✗ Incorrect
Count changes every iteration because it increments or decrements each time through the loop.