Most Frequent Element in Array in C

Summary: This C program finds the most frequent element in an array. If there is a tie, the smallest element among the most frequent ones is returned. It handles both positive and negative numbers by using an offset in the frequency array.

#include <stdio.h>
#include <limits.h>

#define MAX_VALUE 100000
#define OFFSET 100000  // To handle negative values and shift to positive indices

void findMostFrequentElement(int arr[], int n) {
    int freq[2 * MAX_VALUE + 1] = {0};  // Frequency array to store counts of elements
    int max_freq = 0, result = INT_MAX;

    // Count frequencies of each element
    for (int i = 0; i < n; i++) {
        freq[arr[i] + OFFSET]++;  // Increment frequency with offset for negative numbers

        // Check if current element has higher frequency
        if (freq[arr[i] + OFFSET] > max_freq) {
            max_freq = freq[arr[i] + OFFSET];
            result = arr[i];  // Update result to the current most frequent element
        }
        // Resolve tie by choosing the smallest element
        else if (freq[arr[i] + OFFSET] == max_freq && arr[i] < result) {
            result = arr[i];
        }
    }

    // Print the most frequent element
    printf("Most frequent element: %d\n", result);
}

int main() {
    int n;

    // Get the number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    // Check constraints
    if (n < 1 || n > 1000) {
        printf("Invalid number of elements! Please enter a value between 1 and 1000.\n");
        return 1;
    }

    int arr[n];

    // Get the elements of the array
    printf("Enter the elements: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);

        // Check if the element is within the valid range
        if (arr[i] < -MAX_VALUE || arr[i] > MAX_VALUE) {
            printf("Invalid element! Please enter values between -100000 and 100000.\n");
            return 1;
        }
    }

    // Find and print the most frequent element
    findMostFrequentElement(arr, n);

    return 0;
}

Explanation:

Program Overview:

This program identifies the most frequent element in an array. If multiple elements have the same highest frequency, the smallest element among them is chosen.

Constants:

• MAX_VALUE: 100000 - The range limit for input elements.
• OFFSET: 100000 - An offset used to shift negative values to positive indices.

Function - findMostFrequentElement():

This function finds the most frequent element in the array.

• Frequency Array:
  • An array of size 2 * MAX_VALUE + 1 is used to store the frequency of elements.
  • Offset is applied to shift negative values into positive indices.
• Counting Frequencies:
  • Frequencies are counted using freq[arr[i] + OFFSET]++.
  • The element with the highest frequency is tracked using max_freq.
• Handling Ties:
  • If multiple elements have the same frequency, the smaller element is selected.

Main Function Workflow:

1. Input Array Size:
   • The user enters the size of the array n.
   • Constraints ensure that n is between 1 and 1000.
2. Input Array Elements:
   • The user inputs n elements of the array.
   • A validation check ensures that the elements are within the range [-100000, 100000].
3. Find and Print Most Frequent Element:
   • The function findMostFrequentElement() is called to determine and print the most frequent element.

Edge Cases and Error Handling:

• Single Element: If the array has only one element, it is the most frequent.
• Ties: In case of a tie, the smallest element is returned.
• Invalid Element: Elements outside the range [-100000, 100000] are rejected with an error message.

Time Complexity:

• O(n) since each element is processed once to count its frequency.

Space Complexity:

• O(1) because the frequency array size is constant.