find positions of most occurent elem

[glao]

In order to find the most occurent element I am using:

int find( int* arr,  int size )
{ 
  int count = 0, MostOc;
  for ( int i = 0; i < size; i++ ) 
  {
    if ( count == 0 )
    {
        MostOc = arr[i];
    }
    if ( arr[i] == MostOc ) 
        count++;
    else
        count--;
   }
    return MostOc;
}

I can't figure how to return also the positions where the value of the most occurence element is .
For example,for the following code , I should receive that the most occurent element is 14 and it is found at positions 0,4,7,8,12,13,16,17.

#include <stdio.h>
#include <stdlib.h>

int find( int* arr,  int size Arr )
    { 
      int count = 0, MostOc;
      for ( int i = 0; i < sizeArr; i++ ) 
      {
        if ( count == 0 )
        {
            MostOc = arr[i];
        }
        if ( arr[i] == MostOc ) 
            count++;
        else
            count--;
       }
        return MostOc;
    }

int main()
{
  int arr[] = { 14,10, 2, 1,14,1,10,14,14,2,3,4,14,14,1,4,14,14 };
  int N = 18;
  printf("res = %d\n",find(arr,N) );

return 0;
}

[glao]

Hmm. I thought of something like this:

int find( int* arr,  int **pos, int sizeArr ,int *MostOc )
    { 
      int count = 0;
      *pos = (int*)malloc( size * sizeof(int));
      for ( int i =0; i < sizeArr; i++ )
           (*pos)[i] = 999999;


      for ( int i = 0; i < sizeArr; i++ ) 
      {
        if ( count == 0 )
        {
            *MostOc = arr[i];
            (*pos)[i] = i;
        }
        if ( arr[i] == *MostOc ) 
        {
            count++;
             (*pos)[i] = i;
          }
        else
        {
             count--;
             (*pos)[i] = i;
         }
       }
        return MostOc;
    }

and:

int *pos;
int MostOc;

  find( arr,&pos,N,&MOstOc );

  for ( int i = 0; i < N; i++ )
    printf("\nres = %d,pos = %d",MOstOc , pos[i]);

But it in indices where the 14 does not occur it should return 999999 .
But it just returns the index.

[David W]

I would use a struct (with a typedef) to create a data record to track the frequencies of each value in the int array.

Maybe something like this ...

Firstly:

/* most_frequent.c */


#include <stdio.h>
#include <stdlib.h> /* re. malloc */

typedef struct
{
    int val;
    int count;
} ValCount ;

Then some functions:

int update( ValCount* ary, int size, int val )
{
    int i, found = 0;
    for( i = 0; i < size; ++i )
    {
        if( ary[i].val == val )
        {
            ++ary[i].count;
            found = 1;
            break;
        }
    }
    if( !found )
    {
        ValCount tmp;
        tmp.val = val;
        tmp.count = 1;
        ary[size] = tmp;
        ++size;
    }
    return size;
}

int get_i_of_max_count( const ValCount* ary, int size )
{
    int i, i_mc = 0;
    for( i = 1; i < size; ++ i )
    {
        if( ary[i].count > ary[i_mc].count ) i_mc = i;
    }
    return i_mc;
}


void print_positions( const int* ary, int size, int val )
{
    int i;
    for( i = 0; i < size; ++ i )
    {
        if( ary[i] == val ) printf( "%d ", i );
    }
}

Then the main function could be like this:

int main()
{
    int arr[] = { 14, 10, 2, 1, 14, 1, 10, 14, 14, 2, 3, 4, 14, 14, 1, 4, 14, 14 };
    int size = sizeof arr / sizeof *arr ;
    int i, i_mc, size_vc_ary = 0;

    ValCount* vc_ary = malloc( sizeof(ValCount) * size );

    if( vc_ary )
    {
        for( i = 0; i < size; ++ i )
            size_vc_ary = update( vc_ary, size_vc_ary, arr[i] );

        i_mc = get_i_of_max_count( vc_ary, size_vc_ary );

        printf( "The most frequent value was %d and it occured %d times.\n",
                vc_ary[i_mc].val, vc_ary[i_mc].count );
        printf( "The value %d occured at positions: ", vc_ary[i_mc].val );
        print_positions( arr, size, vc_ary[i_mc].val );

        /* free up all dynamic memory when done with it */
        free( vc_ary ); 
    }

    printf( "\n\nPress 'Enter' to continue/exit ... " );
    fflush( stdout );
    return 0;
}

[glao]

Hello ! Excellent solution!Thanks a lot!
If I want to keep in an array the positions ( and not just print them )?

I tried :

int get_i_of_max_count( const ValCount* ary, int size ,int** pos )
{
  int i, i_mc = 0;
  *pos = (int*)malloc( ary[ i_mc ].count* sizeof(int));
  for( i = 1; i < size; ++ i )
  {
    if( ary[ i ].count > ary[ i_mc ].count ) 
    {
      i_mc = i;
      *pos[ i ] = i;
    }
  }

  return i_mc;
}

and in main:

    int *pos;
    i_mc = get_i_of_max_count( vc_ary, size_vc_ary ,&pos );

     for ( int i = 0; i < vc_ary[i_mc].count; i++ )
          printf("pos= %d\n",pos[i]);

but it doesn't work.

[David W]

All you need to do is change the print function to a ....
get and fill array function ...
like this:

void get_positions( const int* ary, int size, int val, int* pos_ary )
{
    int i, j = 0;
    for( i = 0; i < size; ++ i )
    {
        if( ary[i] == val )
            pos_ary[j++] = i;
    }
}

Then, you could update the main function, to be like this:

int main()
{
    int arr[] = { 14, 10, 2, 1, 14, 1, 10, 14, 14, 2, 3, 4, 14, 14, 1, 4, 14, 14 };
    int size = sizeof arr / sizeof *arr ;
    int i, i_mc, size_vc_ary = 0;

    ValCount* vc_ary = malloc( sizeof(ValCount) * size );

    if( vc_ary )
    {
        int* pos_ary;

        for( i = 0; i < size; ++ i )
            size_vc_ary = update( vc_ary, size_vc_ary, arr[i] );

        i_mc = get_i_of_max_count( vc_ary, size_vc_ary );

        printf( "The most frequent value was %d and it occured %d times.\n",
                vc_ary[i_mc].val, vc_ary[i_mc].count );
        printf( "The value %d occured at positions: ", vc_ary[i_mc].val );

        pos_ary = malloc(sizeof(int) * vc_ary[i_mc].count );
        if( pos_ary )
        {
            get_positions( arr, size, vc_ary[i_mc].val, pos_ary );

            for( i = 0; i < vc_ary[i_mc].count; ++ i )
            {
                printf( "%d ", pos_ary[i] );
            }
            /* free up all dynamic memory when done with it */
            free( pos_ary );
        }

        /* free up all dynamic memory when done with it */
        free( vc_ary );
    }

    printf( "\n\nPress 'Enter' to continue/exit ... " );
    fflush( stdout );
    return 0;
}

[glao]

OK, thanks a lot!