c programming help! How to find mode?

Question

How to find mode in an array?

For example: User was asked how many numbers he wants to enter, user enters 5. User then enters the 5 numbers: 1 1 2 3 4.

The output should be: 1

If user enters 1 1 2 2 4
the output should be: 1 2

and if the user enters: 1 2 3 4 5
the output should be: 1 2 3 4 5

I tried finding the mode for hours, I've come closer, but the last number won't show up. Like if I enter 1 2 3 4 5, the output only shows 1 2 3 4. Other codes I've look for wont print the mode if 2 numbers have occur the same number of times. Please help!

Thanks a million!

Answer 1

I'll assume the values aren't necessarily sorted. You can use code like the following. Ignore the readints() function -- it's just a simple state machine used to parse an array of space separated integers and letting the user enter a blank line to quit adding entries. You only need to know what it does, not how it does it.



#include

#include

#include

#include

int readints( FILE * f, int *a, int max ) {

    int s, c, pc, v, n;

        if ( f == NULL || max < 1 ) return 0;

        for ( s= 1, pc= n= v= 0; (c= fgetc( f )) != EOF; pc= c ) {

            if ( !isdigit( c ) ) {

                if ( s == 0 ) {

                    a[n++]= v;

                    if ( n >= max ) return n;

                    s= 1;

                }

                if ( c == '\n' && pc == '\n' ) break;

           } else {

                if ( s == 1 ) { v= 0; s= 0; }

                v *= 10;

                v += c - '0';

            }

        }

    return n;

}

int compare( const void * a, const void * b ) {

    return (*(const int *) a) < (*(const int *) b)? -1 :

           (*(const int *) a) > (*(const int *) b)? 1 : 0;

}

int icompare( const void * a, const void * b ) {

    return compare( *(const int **) a, *(const int **) b );

}

int * modes( int * a, int n ) {

    int i, yn, v, *x, *y, **z, *r;

        qsort( a, n, sizeof( int ), compare );

        x= (int *) malloc( sizeof( int ) * (size_t) n );

        for ( i= 0; i < n-1; ++i ) x[i]= a[i+1] - a[i];

        x[n-1]= INT_MAX;

        y= (int *) malloc( sizeof( int ) * (size_t) n );

        for ( yn= i= 0; i < n; ++i )

            if ( x[i] > 0 ) y[yn++]= i;

        free( x );

        realloc( y, sizeof( int ) * (size_t) yn );

        x= (int *) malloc( sizeof( int ) * (size_t) yn );

        x[0]= y[0]+1;

        for ( i= 1; i < yn; ++i ) x[i]= y[i] - y[i-1];

        z= (int **) malloc( sizeof( int * ) * (size_t) yn );

        for ( i= 0; i < yn; ++i ) z[i]= &x[i];

        qsort( z, yn, sizeof( int * ), icompare );

        for ( v= *z[i= yn-1]; --i >= 0; )

            if ( v != *z[i] ) break;

        r= (int *) malloc( sizeof( int ) * (size_t) (yn-i+2) );

        for ( n= 0; ++i < yn; )

            r[1 + (++n)]= a[y[z[i]-x]];

        r[0]= n;

        r[1]= *z[yn-1];

        qsort( r+2, n, sizeof( int ), compare );

        free( x );

        free( y );

        free( z );

    return r;

}

int main( void ) {

    int i, c, n, *s, vec[200];

        printf( "Enter up to 200 space-separated integers on any number of lines.\n" );

        printf( "Terminate the input by entering a blank line:\n" );

        n= readints( stdin, vec, 200 );

        if ( n < 1 ) return 0;

        s= modes( vec, n );

        n= s[0], c= s[1];

        printf( "Each of the following mode values were repeated %d time(s):\n", c );

        for ( i= 0; i < n; ++i )

            printf( " %d", (int) s[i+2] );

        printf( "\n" );

        free( s );

    return 0;

}



The first link below shows a run at IDEONE.COM with the above code. The second link below shows the algorithm used (in Octave language) in the code to generate the mode value list.

Answer 2

Is the array sorted? If so you need to make two passes through the array. In the first pass you find the longest run of numbers in the array. In the second you report all the runs of the maximum length.



So you might write something like:



void PrintMode(int ar[], size_t size)

{

int maxRunLength = 0;



int currentRunLength = 0;

int currentRunValue = 0;



for (int i = 0 ; i < size ; i++)

{

if (ar[i] != currentRunValue)

{

currentRunLength = 1;

currentRunValue = ar[i];

}

else

{

currentRunLength++;

}



if (maxRunLength < currentRunLength)

{

maxRunLength = currentRunLength;

}

}



for (int i = maxRunLength - 1; i < size ; i++)

{

if (ar[i - maxRunLength + 1] == ar[i])

{

printf("%d\n", ar[i]);

}

}

}

Answer 3

Here's an idea. (It's the idea behind counting sort, in case you're interested)



First, find the maximum element in the array. create another array of that size, set all counters to 0. then go through the original array, and count how many times you see each element. Then go back through the array and find the maximum. Then find all of the maxima.





#include

#include



void enterData(int* arr, int n);

int findMaxElement(int* arr, int n);

void clearArray(int* arr, int n);

void fillInCounts(int* orig, int* counts, int n1, int n2);

int findMaxCount(int* arr, int n);

void printModes(int* arr, int n, int max);



int main(int argc, char* argv[]) {

int n;

printf("How many numbers will you enter? ");

scanf("%d", &n);



/*declare an array to store inputs */

int* original = (int*) malloc (n * sizeof(int));



/* read in the data */

enterData(original, n);



/* find the maximum number inside your array */

int maxElement = findMaxElement(original, n);



/* declare an array that has an index for every possible number in the old array */

int* counts = (int*) malloc ( (maxElement + 1)* sizeof(int));



/* go through the input array and put in the counts for all the elements.

fillInCounts(original, counts, n, maxElement+1);



/* find the frequency which makes up the mode */

int maxCount = findMaxCount(counts, maxElement+1);



/* go back through the counts array and print all modes */

printModes(counts, maxElement+1, maxCount);



return 0;

}





/* this function reads in the data */

void enterData(int* arr, int n) {



int i;

for(i=0; i
printf("Enter number #%d: ", (i+1));

scanf("%d", arr + i);

}



}



/* this function finds the biggest number in the array */

int findMaxElement(int* arr, int n) {



int i;

int max = arr[0];



for(i=1; i
max = arr[i] > max? arr[i]: max;

return max;



}



/* this function sets all counts to 0 */

void clearArray(int* arr, int n) {

int i;



for(i=0; i
arr[i] = 0;



}



/* this goes through the input array and adds one to the counter for that element.

void fillInCounts(int* orig, int* counts, int n1, int n2) {

clearArray(counts, n2);



int i;



for(i=0; i
int pos = arr[i];

counts[pos]++;

}

}

/* finding maxCount of the count array is the same as finding the maxElement in the other array. The reason I bothered writing a new function is to keep the main legible. */

int findMaxCount(int* arr, int n) {

return findMaxElement(arr, n);

}

void printModes(int* arr, int n, int max) {

int i;

for(i=0; i
if(arr[i] ==max)

printf("%d ", i);

}