Tasks Details
hard
Given an array, find all its elements that can become a leader, after increasing by 1 all of the numbers in some segment of a given length.
Task Score
66%
Correctness
100%
Performance
25%
Integers K, M and a non-empty array A consisting of N integers, not bigger than M, are given.
The leader of the array is a value that occurs in more than half of the elements of the array, and the segment of the array is a sequence of consecutive elements of the array.
You can modify A by choosing exactly one segment of length K and increasing by 1 every element within that segment.
The goal is to find all of the numbers that may become a leader after performing exactly one array modification as described above.
Write a function:
vector<int> solution(int K, int M, vector<int> &A);
that, given integers K and M and an array A consisting of N integers, returns an array of all numbers that can become a leader, after increasing by 1 every element of exactly one segment of A of length K. The returned array should be sorted in ascending order, and if there is no number that can become a leader, you should return an empty array. Moreover, if there are multiple ways of choosing a segment to turn some number into a leader, then this particular number should appear in an output array only once.
For example, given integers K = 3, M = 5 and the following array A:
A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 3the function should return [2, 3]. If we choose segment A[1], A[2], A[3] then we get the following array A:
A[0] = 2 A[1] = 2 A[2] = 4 A[3] = 2 A[4] = 2 A[5] = 2 A[6] = 3and 2 is the leader of this array. If we choose A[3], A[4], A[5] then A will appear as follows:
A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = 3 A[6] = 3and 3 will be the leader.
And, for example, given integers K = 4, M = 2 and the following array:
A[0] = 1 A[1] = 2 A[2] = 2 A[3] = 1 A[4] = 2the function should return [2, 3], because choosing a segment A[0], A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the leaders, respectively.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..N];
- each element of array A is an integer within the range [1..M].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 12 minutes
Notes
not defined yet
Code: 06:32:43 UTC,
java,
autosave
Code: 06:43:27 UTC,
cpp,
autosave
Code: 06:43:33 UTC,
cpp,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
// you can use includes, for example:
// you can use includes, for example:
#include <bits/stdc++.h>
using namespace std;
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> solution(int K, int M, vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int>s;
map<int,int> freq;
pair<int,int> maxel=make_pair(0,0);
for(int i=0;i<A.size();i++){
if(freq.find(A[i])!=freq.end()){
freq[A[i]]+=1;
}else{
freq[A[i]]=1;
}
if(maxel.first<freq[A[i]]){
maxel=make_pair(freq[A[i]],A[i]);
}
}
// for(auto it=freq.begin();it!=freq.end();it++){
// cout<< it->first<<":"<<it->second<<"\n";
// }
// priority_queue<pair<int,int> >pq;
// for(auto it=freq.begin();it!=freq.end();it++){
// pq.push({it->second,it->first});
// }
// pq.push({-3,0});
// pq.push({1,2});
// pair<int,int>p1=pq.top();
// cout<<"p1:"<<p1.first<<"\n";
map<int,int> currFreq;
for(int i=0;i<K;i++){
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
}
// cout<<"currFreq:-\n";
for(auto it=currFreq.begin();it!=currFreq.end();it++){
cout<< it->first<<":"<<it->second<<"\n";
int occ=freq[(it->first)+1]+it->second-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[(it->first)+1]);
if(occ>A.size()/2){
s.insert(it->first+1);
}
// if(pq.top().first-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[it->second])>A.size()/2){
// s.insert(pq.top().second);
// }
}
if(maxel.first-(currFreq.find((maxel.second))==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
for(int i=K;i<A.size();i++){
currFreq[A[i-K]]-=1;
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
for(int j=i-K+1;j<=i;j++){
int occ=freq[A[j]+1]+currFreq[A[j]]-(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1]);
// cout<<"A[i]:"<<A[j]<<" freq[A[i]+1]:"<<freq[A[j]+1]<<" currFreq[A[i]]:"<<currFreq[A[j]]<<" (currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1]):"<<(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1])<<"\n";
if(occ>A.size()/2){
s.insert(A[j]+1);
}
}
// if(pq.top().first-(currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1])>A.size()/2){
// s.insert(pq.top().second);
// }
if(maxel.first-(currFreq.find(maxel.second)==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
}
vector<int> ans(s.begin(),s.end());
return ans;
}
int main()
{
vector<int> arr;
arr.push_back(50);
arr.push_back(50);
arr.push_back(50);
arr.push_back(49);
arr.push_back(9);
arr.push_back(49);
arr.push_back(7);
arr.push_back(3);
arr.push_back(7);
vector<int> ans = solution(4, 15, arr);
for (auto it = ans.begin(); it != ans.end(); it++)
{
cout << *it << " ";
}
return 0;
}
Code: 06:43:35 UTC,
cpp,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
// you can use includes, for example:
// you can use includes, for example:
#include <bits/stdc++.h>
using namespace std;
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> solution(int K, int M, vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int>s;
map<int,int> freq;
pair<int,int> maxel=make_pair(0,0);
for(int i=0;i<A.size();i++){
if(freq.find(A[i])!=freq.end()){
freq[A[i]]+=1;
}else{
freq[A[i]]=1;
}
if(maxel.first<freq[A[i]]){
maxel=make_pair(freq[A[i]],A[i]);
}
}
// for(auto it=freq.begin();it!=freq.end();it++){
// cout<< it->first<<":"<<it->second<<"\n";
// }
// priority_queue<pair<int,int> >pq;
// for(auto it=freq.begin();it!=freq.end();it++){
// pq.push({it->second,it->first});
// }
// pq.push({-3,0});
// pq.push({1,2});
// pair<int,int>p1=pq.top();
// cout<<"p1:"<<p1.first<<"\n";
map<int,int> currFreq;
for(int i=0;i<K;i++){
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
}
// cout<<"currFreq:-\n";
for(auto it=currFreq.begin();it!=currFreq.end();it++){
cout<< it->first<<":"<<it->second<<"\n";
int occ=freq[(it->first)+1]+it->second-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[(it->first)+1]);
if(occ>A.size()/2){
s.insert(it->first+1);
}
// if(pq.top().first-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[it->second])>A.size()/2){
// s.insert(pq.top().second);
// }
}
if(maxel.first-(currFreq.find((maxel.second))==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
for(int i=K;i<A.size();i++){
currFreq[A[i-K]]-=1;
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
for(int j=i-K+1;j<=i;j++){
int occ=freq[A[j]+1]+currFreq[A[j]]-(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1]);
// cout<<"A[i]:"<<A[j]<<" freq[A[i]+1]:"<<freq[A[j]+1]<<" currFreq[A[i]]:"<<currFreq[A[j]]<<" (currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1]):"<<(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1])<<"\n";
if(occ>A.size()/2){
s.insert(A[j]+1);
}
}
// if(pq.top().first-(currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1])>A.size()/2){
// s.insert(pq.top().second);
// }
if(maxel.first-(currFreq.find(maxel.second)==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
}
vector<int> ans(s.begin(),s.end());
return ans;
}
// int main()
// {
// vector<int> arr;
// arr.push_back(50);
// arr.push_back(50);
// arr.push_back(50);
// arr.push_back(49);
// arr.push_back(9);
// arr.push_back(49);
// arr.push_back(7);
// arr.push_back(3);
// arr.push_back(7);
// vector<int> ans = solution(4, 15, arr);
// for (auto it = ans.begin(); it != ans.end(); it++)
// {
// cout << *it << " ";
// }
// return 0;
// }
Analysis
Code: 06:43:59 UTC,
cpp,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
// you can use includes, for example:
// you can use includes, for example:
#include <bits/stdc++.h>
using namespace std;
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> solution(int K, int M, vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int>s;
map<int,int> freq;
pair<int,int> maxel=make_pair(0,0);
for(int i=0;i<A.size();i++){
if(freq.find(A[i])!=freq.end()){
freq[A[i]]+=1;
}else{
freq[A[i]]=1;
}
if(maxel.first<freq[A[i]]){
maxel=make_pair(freq[A[i]],A[i]);
}
}
// for(auto it=freq.begin();it!=freq.end();it++){
// cout<< it->first<<":"<<it->second<<"\n";
// }
// priority_queue<pair<int,int> >pq;
// for(auto it=freq.begin();it!=freq.end();it++){
// pq.push({it->second,it->first});
// }
// pq.push({-3,0});
// pq.push({1,2});
// pair<int,int>p1=pq.top();
// cout<<"p1:"<<p1.first<<"\n";
map<int,int> currFreq;
for(int i=0;i<K;i++){
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
}
// cout<<"currFreq:-\n";
for(auto it=currFreq.begin();it!=currFreq.end();it++){
// cout<< it->first<<":"<<it->second<<"\n";
int occ=freq[(it->first)+1]+it->second-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[(it->first)+1]);
if(occ>A.size()/2){
s.insert(it->first+1);
}
// if(pq.top().first-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[it->second])>A.size()/2){
// s.insert(pq.top().second);
// }
}
if(maxel.first-(currFreq.find((maxel.second))==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
for(int i=K;i<A.size();i++){
currFreq[A[i-K]]-=1;
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
for(int j=i-K+1;j<=i;j++){
int occ=freq[A[j]+1]+currFreq[A[j]]-(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1]);
// cout<<"A[i]:"<<A[j]<<" freq[A[i]+1]:"<<freq[A[j]+1]<<" currFreq[A[i]]:"<<currFreq[A[j]]<<" (currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1]):"<<(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1])<<"\n";
if(occ>A.size()/2){
s.insert(A[j]+1);
}
}
// if(pq.top().first-(currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1])>A.size()/2){
// s.insert(pq.top().second);
// }
if(maxel.first-(currFreq.find(maxel.second)==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
}
vector<int> ans(s.begin(),s.end());
return ans;
}
// int main()
// {
// vector<int> arr;
// arr.push_back(50);
// arr.push_back(50);
// arr.push_back(50);
// arr.push_back(49);
// arr.push_back(9);
// arr.push_back(49);
// arr.push_back(7);
// arr.push_back(3);
// arr.push_back(7);
// vector<int> ans = solution(4, 15, arr);
// for (auto it = ans.begin(); it != ans.end(); it++)
// {
// cout << *it << " ";
// }
// return 0;
// }
Analysis
Code: 06:44:07 UTC,
cpp,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
// you can use includes, for example:
// you can use includes, for example:
#include <bits/stdc++.h>
using namespace std;
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> solution(int K, int M, vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int>s;
map<int,int> freq;
pair<int,int> maxel=make_pair(0,0);
for(int i=0;i<A.size();i++){
if(freq.find(A[i])!=freq.end()){
freq[A[i]]+=1;
}else{
freq[A[i]]=1;
}
if(maxel.first<freq[A[i]]){
maxel=make_pair(freq[A[i]],A[i]);
}
}
// for(auto it=freq.begin();it!=freq.end();it++){
// cout<< it->first<<":"<<it->second<<"\n";
// }
// priority_queue<pair<int,int> >pq;
// for(auto it=freq.begin();it!=freq.end();it++){
// pq.push({it->second,it->first});
// }
// pq.push({-3,0});
// pq.push({1,2});
// pair<int,int>p1=pq.top();
// cout<<"p1:"<<p1.first<<"\n";
map<int,int> currFreq;
for(int i=0;i<K;i++){
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
}
// cout<<"currFreq:-\n";
for(auto it=currFreq.begin();it!=currFreq.end();it++){
// cout<< it->first<<":"<<it->second<<"\n";
int occ=freq[(it->first)+1]+it->second-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[(it->first)+1]);
if(occ>A.size()/2){
s.insert(it->first+1);
}
// if(pq.top().first-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[it->second])>A.size()/2){
// s.insert(pq.top().second);
// }
}
if(maxel.first-(currFreq.find((maxel.second))==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
for(int i=K;i<A.size();i++){
currFreq[A[i-K]]-=1;
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
for(int j=i-K+1;j<=i;j++){
int occ=freq[A[j]+1]+currFreq[A[j]]-(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1]);
// cout<<"A[i]:"<<A[j]<<" freq[A[i]+1]:"<<freq[A[j]+1]<<" currFreq[A[i]]:"<<currFreq[A[j]]<<" (currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1]):"<<(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1])<<"\n";
if(occ>A.size()/2){
s.insert(A[j]+1);
}
}
// if(pq.top().first-(currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1])>A.size()/2){
// s.insert(pq.top().second);
// }
if(maxel.first-(currFreq.find(maxel.second)==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
}
vector<int> ans(s.begin(),s.end());
return ans;
}
// int main()
// {
// vector<int> arr;
// arr.push_back(50);
// arr.push_back(50);
// arr.push_back(50);
// arr.push_back(49);
// arr.push_back(9);
// arr.push_back(49);
// arr.push_back(7);
// arr.push_back(3);
// arr.push_back(7);
// vector<int> ans = solution(4, 15, arr);
// for (auto it = ans.begin(); it != ans.end(); it++)
// {
// cout << *it << " ";
// }
// return 0;
// }
Analysis
Code: 06:44:15 UTC,
cpp,
final,
score:
66
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
// you can use includes, for example:
// you can use includes, for example:
#include <bits/stdc++.h>
using namespace std;
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> solution(int K, int M, vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int>s;
map<int,int> freq;
pair<int,int> maxel=make_pair(0,0);
for(int i=0;i<A.size();i++){
if(freq.find(A[i])!=freq.end()){
freq[A[i]]+=1;
}else{
freq[A[i]]=1;
}
if(maxel.first<freq[A[i]]){
maxel=make_pair(freq[A[i]],A[i]);
}
}
// for(auto it=freq.begin();it!=freq.end();it++){
// cout<< it->first<<":"<<it->second<<"\n";
// }
// priority_queue<pair<int,int> >pq;
// for(auto it=freq.begin();it!=freq.end();it++){
// pq.push({it->second,it->first});
// }
// pq.push({-3,0});
// pq.push({1,2});
// pair<int,int>p1=pq.top();
// cout<<"p1:"<<p1.first<<"\n";
map<int,int> currFreq;
for(int i=0;i<K;i++){
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
}
// cout<<"currFreq:-\n";
for(auto it=currFreq.begin();it!=currFreq.end();it++){
// cout<< it->first<<":"<<it->second<<"\n";
int occ=freq[(it->first)+1]+it->second-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[(it->first)+1]);
if(occ>A.size()/2){
s.insert(it->first+1);
}
// if(pq.top().first-(currFreq.find((it->first)+1)==currFreq.end()?0:currFreq[it->second])>A.size()/2){
// s.insert(pq.top().second);
// }
}
if(maxel.first-(currFreq.find((maxel.second))==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
for(int i=K;i<A.size();i++){
currFreq[A[i-K]]-=1;
if(currFreq.find(A[i])!=freq.end()){
currFreq[A[i]]+=1;
}else{
currFreq[A[i]]=1;
}
for(int j=i-K+1;j<=i;j++){
int occ=freq[A[j]+1]+currFreq[A[j]]-(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1]);
// cout<<"A[i]:"<<A[j]<<" freq[A[i]+1]:"<<freq[A[j]+1]<<" currFreq[A[i]]:"<<currFreq[A[j]]<<" (currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1]):"<<(currFreq.find(A[j]+1)==currFreq.end()?0:currFreq[A[j]+1])<<"\n";
if(occ>A.size()/2){
s.insert(A[j]+1);
}
}
// if(pq.top().first-(currFreq.find(A[i]+1)==currFreq.end()?0:currFreq[A[i]+1])>A.size()/2){
// s.insert(pq.top().second);
// }
if(maxel.first-(currFreq.find(maxel.second)==currFreq.end()?0:currFreq[maxel.second])>A.size()/2){
s.insert(maxel.second);
}
}
vector<int> ans(s.begin(),s.end());
return ans;
}
// int main()
// {
// vector<int> arr;
// arr.push_back(50);
// arr.push_back(50);
// arr.push_back(50);
// arr.push_back(49);
// arr.push_back(9);
// arr.push_back(49);
// arr.push_back(7);
// arr.push_back(3);
// arr.push_back(7);
// vector<int> ans = solution(4, 15, arr);
// for (auto it = ans.begin(); it != ans.end(); it++)
// {
// cout << *it << " ";
// }
// return 0;
// }Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N*(N+M)) or O(N**2)
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
expand all
Performance tests
medium_tests1
medium tests (N = 10000, M = 100)
medium tests (N = 10000, M = 100)
✘
TIMEOUT ERROR
running time: 0.424 sec., time limit: 0.100 sec.
running time: 0.424 sec., time limit: 0.100 sec.
1.
0.424 s
TIMEOUT ERROR,
running time: 0.424 sec., time limit: 0.100 sec.
2.
0.020 s
OK
3.
0.020 s
OK
medium_tests2
medium tests(N >= 20000, M=30000)
medium tests(N >= 20000, M=30000)
✘
TIMEOUT ERROR
running time: 2.024 sec., time limit: 0.100 sec.
running time: 2.024 sec., time limit: 0.100 sec.
1.
0.048 s
OK
2.
2.024 s
TIMEOUT ERROR,
running time: 2.024 sec., time limit: 0.100 sec.
3.
2.356 s
TIMEOUT ERROR,
running time: 2.356 sec., time limit: 0.100 sec.
1.
0.024 s
OK
2.
0.040 s
OK
3.
0.012 s
OK
1.
0.012 s
OK
2.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.