Question

How to find elements that appear more than list_size/K times in a list with C

Answer 1

#include <stdio.h>

void elements_that_appear_more_than_x_times(int arr[], int size, int k) {
    int times = size / k;
    
    printf("more than %d times\n", times);

    for (int i = 0; i < size; i++) {
         int count = 1;

        if (arr[i] != -1) {
            for (int j = i + 1; j < size; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                    arr[j] = -1; // -1 to avoid repetition, but kill part of the array values...
                }
            }
        }
        
        if (count > times) {
            printf("%d ",arr[i]);
        }
    }
}

int main() {
    int arr[] = {4, 8, 6, 5, 5, 8, 3, 2, 1, 2, 2, 5, 5, 5, 5, 8, 9, 8, 8};
    int k = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    
    elements_that_appear_more_than_x_times(arr, size, k);
    
    return 0;
}




/*
run:

more than 4 times
8 5 

*/

 

70+ SQL courses for beginners and professionals

Answer 2

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

void elements_that_appear_more_than_x_times(int arr[], int size, int k) {
    int times = size / k;
    
    int *tmparr = (int*)malloc(size * sizeof(int));
    
    for (int i = 0; i < size; i++) {
        tmparr[i] = arr[i];
    }
    
    printf("more than %d times\n", times);

    for (int i = 0; i < size; i++) {
        int count = 1;

        if (tmparr[i] != -1) {
            for (int j = i + 1; j < size; j++) {
                if (tmparr[i] == tmparr[j]) {
                    count++;
                    tmparr[j] = -1; 
                }
            }
        }
        
        if (count > times) {
            printf("%d\n",tmparr[i]);
        }
    }
    
    free(tmparr);
}

int main() {
    int arr[] = {4, 8, 6, 5, 5, 8, 3, 2, 1, 2, 2, 5, 5, 5, 5, 8, 9, 8, 8};
    int k = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    
    elements_that_appear_more_than_x_times(arr, size, k);

    return 0;
}



/*
run:

more than 4 times
8
5

*/

 

70+ SQL courses for beginners and professionals

Answer 3

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

typedef struct {
    int key;
    int value;
} KeyValuePair;

KeyValuePair* create_freqency(int size) {
    KeyValuePair* freqency = (KeyValuePair*)malloc(size * sizeof(KeyValuePair));
    
    for (int i = 0; i < size; i++) {
        freqency[i].key = 0;
        freqency[i].value = 0;
    }
    
    return freqency;
}

int find_index(KeyValuePair* freqency, int size, int key) {
    for (int i = 0; i < size; i++) {
        if (freqency[i].key == key) {
            return i;
        }
    }
    
    return -1;
}

void elements_that_appear_more_than_x_times(int* arr, int size, int k) {
    int times = size / k;
    KeyValuePair* freqency = create_freqency(size);
    int unique_elements = 0;
    
    printf("more than %d times\n", times);

    for (int i = 0; i < size; i++) {
        int index = find_index(freqency, unique_elements, arr[i]);
        if (index != -1) {
            freqency[index].value += 1;
        } else {
            freqency[unique_elements].key = arr[i];
            freqency[unique_elements].value = 1;
            unique_elements++;
        }
    }

    for (int i = 0; i < unique_elements; i++) {
        if (freqency[i].value > times) {
            printf("%d\n", freqency[i].key);
        }
    }

    free(freqency);
}

int main() {
    int arr[] = {4, 8, 6, 5, 5, 8, 3, 2, 1, 2, 2, 5, 5, 5, 5, 8, 9, 8, 8};
    int k = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    
    elements_that_appear_more_than_x_times(arr, size, k);
    
    return 0;
}



/*
run:

more than 4 times
8
5

*/

 

70+ SQL courses for beginners and professionals