I'm writing an implementation of the Moore Voting algorithm for finding the majority element (i.e. the element which occurs more than size/2 times) in an array. The code should return the majority element if it exists or else it should return -1. Now my version of the majorityElement(int size, int arr[]) seems to work perfectly fine if I directly hardcode the integer array in the main() function and invoke it from there.
int majorityElement(int size, int arr[])
{
int majorityindex = 0;
int votes = 1;
int index;
for (index = 1; index < size; index++)
{
if (arr[index] == arr[majorityindex])
votes++;
else
votes--;
if (votes == 0)
{
majorityindex = index;
votes = 1;
}
}
int count = 0;
int i;
for (i = 0; i < size; i++)
{
if(arr[majorityindex] == arr[i])
count++;
}
if (count > (size/2))
return arr[majorityindex];
return -1;
}
However, I'm facing some issues if I try to read an input stream like these:
2
5
3 1 3 3 2
3
1 2 3
The first line of the input contains the number of test cases. The first line of the test case will be the size of the array and the second line will be the elements of the array.
I tried to read the input stream from within the main() function like this:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
int majorityElement(int size, int arr[]);
int main()
{
char buf[3];
fgets(buf, MAX, stdin);
int n = atoi(buf);
char a[3];
char b[MAX];
int i;
int count;
int* num;
for (i = 0; i < n; i++)
{
count = 0;
fgets(a, MAX, stdin);
fgets(b, MAX, stdin);
int x = atoi(a);
char* num[x];
int arr[x];
int k = 0;
char* token = strtok(b, " ");
while (token != NULL)
{
num[k] = token;
arr[k] = atoi(num[k]);
token = strtok(NULL, " ");
k++;
}
printf("%d\n", majorityElement(x, arr));
}
return 1;
}
I took the size of buf[] and a[] as 3 during declaration as they must have sufficient space for the \n character read by fgets() as well as the terminating \0 character. As far as I know, the atoi() function ignores the \n character while converting the character array (string) into an integer. I tried to store the first entry of the input (i.e. the number of entries) in a character array buf, converted it into a string and stored it in a variable n. Similarly, I tried to obtain the size of a test array in a variable x and the test arrays (second line of test case) in an integer array arr. While buf and n seem to obtain the correct values in all cases, I'm not quite sure about arr. I'm aware that fgets() leaves a terminal \n character and that might be causing some havoc during tokenization using strtok, although I can't finger at why. I tried submitting this code on GeeksForGeeks. It gives absolutely correct outputs for the sample test case:
2
5
3 1 3 3 2
3
1 2 3
that is
3
-1
However, when I try to "submit" my solution it says:
Possibly your code doesn't work correctly for multiple test-cases (TCs).
The first test case where your code failed:
Input:
4
1 2 2 1
Its Correct output is:
-1
And Your Code's output is:
1
I can't seem to make sense of this. If I manually write this in stdin:
1
4
1 2 2 1
the code outputs
-1
which is indeed the correct solution. This doesn't match with the output claimed during the submission i.e. 1. So I'm not really sure where I'm going wrong. Have I used fgets() or strtok() incorrectly in the main() function? Or is it something else?
Updated the main() function according to suggestions in the comments.
int main()
{
char buf[MAX];
fgets(buf, MAX, stdin);
int n = atoi(buf);
char a[MAX];
char b[MAX];
int i;
int count;
int* num;
for (i = 0; i < n; i++)
{
count = 0;
fgets(a, MAX, stdin);
fgets(b, sizeof(a), stdin);
a[sizeof(a)-1] = '\0';
b[sizeof(b)-1] = '\0';
int x = atoi(a);
int arr[x];
int k = 0;
char* token = strtok(b, " ");
while (token != NULL)
{
if (k > x)
break;
arr[k] = atoi(token);
token = strtok(NULL, " ");
k++;
}
printf("%d\n", majorityElement(x, arr));
}
return 1;
}
As pointed out by @Vlad, the MAX was set too low in my original array. The question says that the number of entries in an array is upper bounded by 10^7 and each array entry is upper bounded by 10^6 (7 digits). So MAX needs to be of the order 10^8. According to the suggestions in the comments, I'm now using dynamic allocation instead of variable length arrays.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10000000
int majorityElement(int size, int arr[])
{
int majorityindex = 0;
int votes = 1;
int index;
for (index = 1; index < size; index++)
{
if (arr[index] == arr[majorityindex])
votes++;
else
votes--;
if (votes == 0)
{
majorityindex = index;
votes = 1;
}
}
int count = 0;
int i;
for (i = 0; i < size; i++)
{
if(arr[majorityindex] == arr[i])
count++;
}
if (count > (size/2))
return arr[majorityindex];
return -1;
}
int main()
{
char* buf = calloc (MAX, sizeof(char));
fgets(buf, MAX, stdin);
int n = atoi(buf);
char* a = calloc (MAX, sizeof(char));
char* b = calloc(MAX, sizeof(char));
int i;
for (i = 0; i < n; i++)
{
fgets(a, MAX, stdin);
fgets(b, MAX, stdin);
a[strlen(a)-1] = '\0';
b[strlen(b)-1] = '\0';
int x = atoi(a);
int *arr = calloc(x, sizeof(int));
int k = 0;
char* token = strtok(b, " ");
while (token != NULL)
{
if (k > x)
break;
arr[k] = atoi(token);
token = strtok(NULL, " ");
k++;
}
printf("%d\n", majorityElement(x, arr));
free(arr)
}
free(buf);
free(a);
free(b);
return 1;
}
If I set MAX to 10^7 then the code passes all the test cases and is accepted for submission. However, if I set MAX to 10^8 (as required), I get a segmentation fault. How to overcome this?
