Skip to content

Instantly share code, notes, and snippets.

@BroVic
Created January 30, 2022 14:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save BroVic/6606db42eb3d5580dc19d07464ebb718 to your computer and use it in GitHub Desktop.
Save BroVic/6606db42eb3d5580dc19d07464ebb718 to your computer and use it in GitHub Desktop.
MaxCounter [Codility Lesson in C++]
#include <vector>
#include <numeric>
#include <unordered_map>
#include <algorithm>
#include <iostream>
std::vector<int> solution(int N, std::vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
// for each element of the list
// if the element at the position is same as `max` i.e. it doesn't exist in monitor
// - create the element in monitor
// - increment the value by 1
// when the N + 1 element is reached
// - find the maximum value in the monitor and reset max with it.
// Destroy the monitor
auto max = 0;
std::unordered_map<int, int> monitor;
for (const auto X : A)
{
auto startIter = monitor.begin();
auto lastIter = monitor.end();
if (X == (N + 1))
{
if (!monitor.empty())
{
const auto maxpairIter = std::max_element(startIter, lastIter,
[](const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second < b.second;
});
max = maxpairIter->second;
}
monitor.clear();
continue;
}
if (monitor.find(X) == lastIter)
{
const auto elem = std::make_pair(X, max);
monitor.insert({elem});
}
++monitor[X];
}
std::vector<int> counters(N, max);
for (const auto& kvpair : monitor)
{
const auto index = kvpair.first - 1;
counters[index] = kvpair.second;
}
return counters;
}
int main()
{
std::vector<int> v{3, 4, 8, 2, 1, 2, 6, 5, 7, 7, 8, 8, 1};
const auto ans = solution(7, v);
std::cout << "( ";
for (const auto n : ans)
{
std::cout << n << " ";
}
std::cout << ")\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment