How to find the element with minimum occurrences in an array with C

1 Answer

0 votes
#include <stdio.h>
#include <stdlib.h>
 
// Comparison function required by standard qsort
int compare_ints(const void *a, const void *b) {
    int arg1 = *(const int *)a;
    int arg2 = *(const int *)b;
 
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
 
    return 0;
}
 
// Function to find the element with minimum occurrences
// Returns 1 on success, 0 on failure (e.g., empty array or memory allocation error)
int find_min_occurrence(const int *arr, size_t size, int *result) {
    if (arr == NULL || size == 0) {
        return 0; // Return failure for invalid inputs
    }
 
    // 1. Create a dynamic copy of the array so original data is preserved
    int *sorted = (int *)malloc(size * sizeof(int));
    if (sorted == NULL) {
        return 0; // Allocation failure
    }
 
    for (size_t i = 0; i < size; i++) {
        sorted[i] = arr[i];
    }
 
    // 2. Sort the array in-place O(N log N)
    qsort(sorted, size, sizeof(int), compare_ints);
 
    // 3. Single pass to count consecutive runs
    int min_element = sorted[0];
    size_t min_count = size + 1; // Initialize higher than any possible count
 
    size_t current_count = 1;
    for (size_t i = 1; i <= size; i++) {
        // If still on the same element, increment counter
        if (i < size && sorted[i] == sorted[i - 1]) {
            current_count++;
        } else {
            // End of a group: check if this group's count is smaller than min_count
            if (current_count < min_count) {
                min_count = current_count;
                min_element = sorted[i - 1];
            }
            current_count = 1; // Reset counter for next unique element
        }
    }
 
    // 4. Clean up dynamically allocated memory
    free(sorted);
 
    *result = min_element;
     
    return 1; // Return success flag
}
 
int main(void) {
    int arr[] = {1, 3, 1, 1, 4, 4, 5, 5, 4, 2, 2, 2, 3, 3, 3};
    size_t size = sizeof(arr) / sizeof(arr[0]);
 
    int min_item;
    if (find_min_occurrence(arr, size, &min_item)) {
        printf("%d\n", min_item); // Output: 5
    } else {
        printf("Error processing array.\n");
    }
 
    return 0;
}
 
 
/*
run:
 
5
 
*/

 



answered Sep 25 by avibootz
edited Sep 25 by avibootz
...