Sponsored
Sponsored
This approach uses a hash map (or dictionary) to count occurrences of elements in the data. By iterating through the data once to populate the hash map, we can achieve efficient lookups. The main idea is to traverse the input list, counting occurrences of each element, and storing these counts in a hash map for quick access in the future.
Time Complexity: O(n) for traversing the list once.
Space Complexity: O(k), where k is the range of input values (determined by MAX).
1#include <stdio.h>
2#include <stdlib.h>
3
4#define MAX 10000 // Adjust based on constraints
5
6int main() {
7 int n, x;
8 printf("Enter number of elements: ");
9 scanf("%d", &n);
10 int count[MAX] = {0};
11
12 printf("Enter the elements (0 <= element < %d):\n", MAX);
13 for (int i = 0; i < n; i++) {
14 scanf("%d", &x);
15 count[x]++;
16 }
17
18 // Now, count contains the frequency of each element
19 // Example query
20 printf("Enter element to query: ");
21 scanf("%d", &x);
22 printf("Element %d appears %d times\n", x, count[x]);
23
24 return 0;
25}This C program sets up an array to count the frequency of each element in a list. It assumes input values are non-negative and less than MAX. We use a simple array count to store the tally of each integer that appears in the input list.
By sorting the input list, elements of the same value will be grouped together. We can then iterate through the sorted list to count the occurrences of each element. This takes advantage of the property of sorting to simplify the counting process.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) additional space for counting.
1#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
vector<int> arr(n);
cout << "Enter the elements:\n";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
sort(arr.begin(), arr.end());
cout << "Sorted elements for counting:\n";
int current = arr[0];
int count = 1;
for (int i = 1; i < n; ++i) {
if (arr[i] == current) {
count++;
} else {
cout << "Element " << current << " appears " << count << " times\n";
current = arr[i];
count = 1;
}
}
cout << "Element " << current << " appears " << count << " times\n";
return 0;
}This C++ program leverages the sort function from the Standard Template Library (STL) to sort the input, then counts identical elements by iterating over the sorted array.