count repeated elements in an array [closed]

prev = input[0];
count = 1;
for (i = 1; i < ARRAYSIZE; i++)
{
  if (input[i] == prev) count++;
  else
  {
    printf("%d=%d ", prev, count);
    prev = input[i];
    count = 1;
  }
}
// Printing the last element
printf("%d=%d ", prev, count);

if it's already sorted, there may be a faster way

Split the list into halves. deal with each section in this way: test the first and last nubmer. If they're the same, you know the result. if it's not the same, split it in the middle and recurse over each half again.

With long runs of the same number, this will be efficient. It should revert to the one-by-one method if a section is small. You could sample the data at random spots, testing s, s+1, to get a percentage of the time a number increases from its predecessor. The higher than number is, the earlier you should switch to one-by-one method.

This method is also parallelizable.

It seems the array is sorted (According to the example). If so you just have to pick the first element and iterate through the array until a distinct value is found. Within this process you can have a counter within loop to count the occurences.

Then pick the found distinct value instead of first element and repeat the process.

If the range of values are small, you can have another array holding the count of each element, pretty much like counting sort. If the range of values is large, you'll need a hash table.

A good method is to iterate through the elements in the array and count up how many of each one that you see. Once you have finished, you print out the counts that you got.

void count_elements(int * pArray, long nElements)
{
    int * pStart;
    for ( pStart = pArray++; nElements > 1; nElements--, pArray++ )
    {
        if ( *pStart != *pArray )
        {
            printf("%i = %u ", *pStart, (pArray - pStart));
            pStart = pArray;
        }
    }
    printf("%i = %u ", *pStart, (pArray - pStart));
}

Easy example explained.

// Count each element create a sorted hash to hold each unique element from the original array (could also be done as a linked list) read each element from the array if the hash element already exists increase the count (value) of that key if the hash element does not exist create a key value pair (value = 1) loop

// Print each element loop through the key's of the hash and printf("%d: %d\n", key, value); if you need to represent zero values as well, implement a lastKey and do a key to lastKey comparison to determine if a key was zero

Sort and simple program/function

handled:
1) end of array item
2) empty case
3) singleton case

#include <stdio.h>

int main() {

  int input[] = {1,1,1,1,2,2,2,3,3,4};

  if (sizeof(input) == 0) return 0;

  int prev = input[0];
  int count = 1;
  int i;
  int ARRAYSIZE = sizeof(input) / sizeof(int);

  for (i = 1; i < ARRAYSIZE; i++) {
    if (input[i] == prev) {
      count++;
    } else {
      printf("%d=%d ", prev, count);
      prev = input[i];
      count = 1;
    }

  }
  printf("%d=%d\n", prev, count);
  return 0;
}

and the test cases:

when input is {}
-----------------------------------
jianlin@ubuntu:~$ gcc try.c
jianlin@ubuntu:~$ ./a.out

when input is {123}
-----------------------------------
jianlin@ubuntu:~$ gcc try.c
jianlin@ubuntu:~$ ./a.out
123=1 

when input is {1,123}
-----------------------------------
jianlin@ubuntu:~$ gcc try.c
jianlin@ubuntu:~$ ./a.out
1=1 123=1 

when input is {1,1,1,1,2,2,2,3,3,4}
-----------------------------------
jianlin@ubuntu:~$ gcc try.c
jianlin@ubuntu:~$ ./a.out
1=4 2=3 3=2 4=1 

when input is {1,1,1,1,2,2,2,3,3,4,4}
-----------------------------------
jianlin@ubuntu:~$ gcc try.c
jianlin@ubuntu:~$ ./a.out
1=4 2=3 3=2 4=2