Home > Software engineering >  How do I stop counting duplicates of a particular value after its already counted once in an array i
How do I stop counting duplicates of a particular value after its already counted once in an array i

Time:09-17

For example I have an array:

arr[9] = {1, 3, 4, 9, 2, 9, 2, 9, 7}

I then sort the array to get

arr[9] = {1, 2, 2, 3, 4, 7, 9, 9, 9}

Then I count duplicates for each value using two for loops. The output I want is:

2 instances of 2
3 instances of 9

Instead, I get:

2 instances of 2
3 instances of 9
2 instances of 9

I know that after the loop goes once, when arr[6], the outer loop counts that there are two more 9 but after that is finished, and loop goes to arr[7], the outer loop still counts there is another 9 which is arr[8]. So my question, how do I stop the code when it has counted duplicates for each number in the array once. Thanks!

Example code:

#define NUM = 9
int main() {
    arr[NUM] = {1, 3, 4, 9, 2, 9, 2, 9, 7};
    sort_int_array(arr, NUM); //insertion sort function

    int i, j, count=1;
    for (i=0; i<NUM; i  ) {
        for (j=i 1;j<NUM; j  ) {
            if (arr[i] == arr[j]) {
                count  ;
            }
            if (arr[i] != arr[j] && count>1) {
                printf("%d instances of %d\n", count, arr[i]);
                count=1;
            }
        }
    }
}

CodePudding user response:

I found the answer guys, thank you for helping. I just needed to remove the 2nd for loop.

#define NUM = 9
int main() {
    arr[NUM] = {1, 3, 4, 9, 2, 9, 2, 9, 7};
    sort_int_array(arr, NUM); //insertion sort function

    int i, count=1;
    for (i=0; i<NUM; i  ) {
        if (arr[i] == arr[i 1]) {
            count  ;
        }
        if (arr[i] != arr[i 1] && count>1) {
            printf("%d instances of %d\n", count, arr[i]);
            count=1;
        }
    }
}

CodePudding user response:

I think the problem is you go to the first nine, then it counts the next two. THEN it will go to the duplicate and also compare the duplicate against the other duplicate. I assume what you could do is check if arr[i] is not equal to arr[i - 1] so you don't compare duplicates

CodePudding user response:

Here is a demonstrative program that shows how numbers of occurrences of elements of an array cam be calculated.

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

int cmp( const void *a, const void *b )
{
    int x = *( const int * )a;
    int y = *( const int * )b;
    
    return ( y < x ) - ( x < y );
}

int main(void) 
{
    int arr[] = {1, 3, 4, 9, 2, 9, 2, 9, 7};
    const size_t N = sizeof( arr ) / sizeof( *arr );
    
    qsort( arr, N, sizeof( int ), cmp );
    
    for ( size_t i = 0; i != N; )
    {
        size_t j = i;
        size_t count = 1;
        while (   i != N && arr[i] == arr[j] )   count;

        printf( "%zu instances of %d\n", count, arr[j] );       
    }
    
    return 0;
}

The program output is

1 instances of 1
2 instances of 2
1 instances of 3
1 instances of 4
1 instances of 7
3 instances of 9

If you want you may substitute this call of printf

printf( "%zu instances of %d\n", count, arr[j] );

    

for this one

if ( count != 1 ) printf( "%zu instances of %d\n", count, arr[j] );

In this case the output will be

2 instances of 2
3 instances of 9

EDIT: As for your solution published as an answer to your own question then the code invokes undefined behavior due to accessing memory beyond the array in this expression arr[i 1] when i is equal to NUM - 1

for (i=0; i<NUM; i  ) {
    if (arr[i] == arr[i 1]) {
                  ^^^^^^^^  
        count  ;
    }
    if (arr[i] != arr[i 1] && count>1) {
                  ^^^^^^^^
        printf("%d instances of %d\n", count, arr[i]);
        count=1;
    }
}

CodePudding user response:

You don't need to use two for loops for this, it would be inefficient and increases the complexity of the code.

If you are doing this with hand you would

  1. Bring another sheet of paper.
  2. for each number in the array:
    • if it's the first time you see this number:
      Note it down and record it has count of 1
    • else:
      then increment the count by 1

if you only need elements that occurred at least twice, you can filter out elements with count = 1.

As for the code:

// this is called frequency array, which we will use to store the 
// number of occurrences (frequency) of a given number.
// The size of the array must be larger than the largest number in the array
int sz = 10  // sz = largest expected element   1 (this only works for array of integers).
int freq[sz];

memset(freq, 0, sz * sizeof(int));  // reset all values in the array to 0

int arr[9] = {1, 2, 2, 3, 4, 7, 9, 9, 9};
int i;

for (i = 0;i < 9;i  ){
    cur = arr[i]; // read the current element
    freq[cur]  = 1;  // increment its count by 1
}

for (i = 0;i < sz;i  ) {
    count = freq[i];   // read the count of the number i
    if(count != 0) {
        // a count of 0 means that the number didn't occur in the array
        // you can also exclude numbers occurring only once by count > 1
        printf("%d instances of %d\n", count, i);
    }
}

I didn't test this code but this is the concept, you can find more here.

This implementation uses more space than needed, but it has fast access time, if you move to cpp, you can use stl map or unordered_map for more space-efficient solution.

  • Related