#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
int findNthMostRareElement(const std::vector<int>& arr, int n) {
std::unordered_map<int, int> frequencyMap;
for (int element : arr) {
frequencyMap[element]++;
}
std::vector<std::pair<int, int>> sortedFrequency;
for (const auto& entry : frequencyMap) {
sortedFrequency.emplace_back(entry.first, entry.second);
}
std::sort(sortedFrequency.begin(), sortedFrequency.end(),
[](const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second < b.second;
});
if (n > sortedFrequency.size()) {
return -1; // Invalid input, nth most rare element doesn't exist
}
return sortedFrequency[n - 1].first;
}
int main() {
std::vector<int> arr = {4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4};
int n = 3; // Find the 3rd most rare element
int result = findNthMostRareElement(arr, n);
if (result != -1) {
std::cout << "The " << n << "th most rare element is: " << result << std::endl;
} else {
std::cout << "Invalid input. The array does not have " << n << " rare elements." << std::endl;
}
return 0;
}