CODEWITHSUNDEEP
arrayscmalloc
Drakonus
Drakonus

Reputation: 11

The fastest and most efficient way to find the number of distinct elements of a 1D array

So I'm very new to programming and the C language, and I would like to find the simplest, fastest, and most efficient way to count all the distinct elements of a 1D array. This was actually for a school assignment, but I've been stuck on this problem for days, since my program was apparently too slow for the online judge and it got a TLE. I've used regular arrays and dynamically allocated arrays using malloc, but neither worked.

Anyways, here's the latest code of it(using malloc):

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

int distinct(int *arr, int N){
    
    int j, k, count = 1;
    
    for(j = 1; j < N; j++){
        for(k = 0; k < j; k++){
            if(arr[j] == arr[k]){
                break;
            }
        }
        if(j == k){
            count++;
        }
    }
    
    return count;
}

int main(){
    
    int T, N, i = 0;
    
    scanf("%d", &T);
    
    do{
        scanf("%d", &N);
        int *arr;
        arr = (int*)malloc(N * sizeof(int));
        for(int j = 0; j < N; j++){
            scanf("%d", &arr[j]);
        }
        int count = distinct(arr, N);
        printf("Case #%d: %d\n", i + 1, count);
        i++;
    }while(i < T);
    
    return 0;
}

Upvotes: 1

Views: 1376

Answers (1)

Ted Lyngmo
Ted Lyngmo

Reputation: 117573

The most efficient way depends on too many unknown factors. One way is to sort the array and then to count distinct elements in there, skipping the duplicates as you go. If you have sorted the array and gotten this:

1 1 1 1 2 2 2 2 3 3
^       ^       ^
+-skip--+-skip--+-- end

... you can easily see that there are 3 distinct values in there.

If you don't have a favourite sorting algorithm handy, you could use the built-in qsort function:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

Example:

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

int compar(const void *l, const void *r) {
    const int* lhs = l;
    const int* rhs = r;
    if(*lhs < *rhs) return -1; // left side is less than right side: -1
    if(*lhs > *rhs) return 1;  // left side is greater than right side: 1
    return 0;                  // they are equal: 0
}

int distinct(int arr[], int N){
    // sort the numbers
    qsort(arr, N, sizeof *arr, compar);

    int count = 0;
    for(int i=0; i < N; ++count) {
        int curr = arr[i];
        // skip all numbers equal to curr as shown in the graph above:
        for(++i; i < N; ++i) {
            if(arr[i] != curr) break;
        }
    }
    return count;
}

int main() {
    int T, N, i = 0;
    
    if(scanf("%d", &T) != 1) return 1; // check for errors
    
    while(T-- > 0) { 
        if(scanf("%d", &N) != 1) return 1;

        int *arr = malloc(N * sizeof *arr);
        if(arr == NULL) return 1; // check for errors

        for(int j = 0; j < N; j++){
            if(scanf("%d", &arr[j]) != 1) return 1;
        }

        int count = distinct(arr, N);

        free(arr); // free after use

        printf("Case #%d: %d\n", ++i, count);
    }
}

Upvotes: 1

Related Questions