#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
*/