Algorithm and C Program to Find an Element Appearing More Than n/2 Times
C
Hard
3 views
Problem Description
Finding majority element in array that appears no/more than 2 times - How does the logic of count increment/decrement work while maintaining candidates?
Official Solution
#include <stdio.h>
int main() {
int arr[100], n, i;
int candidate, count = 0, freq = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter array elements:n");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Phase 1: Find candidate
for (i = 0; i < n; i++) {
if (count == 0) {
candidate = arr[i];
count = 1;
} else if (arr[i] == candidate) {
count++;
} else {
count--;
}
}
// Phase 2: Verify candidate
for (i = 0; i < n; i++) {
if (arr[i] == candidate) {
freq++;
}
}
if (freq > n / 2) {
printf("Majority element is: %dn", candidate);
} else {
printf("No majority element foundn");
}
return 0;
}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!