Tasks Details
medium
1.
Buckets
Given N buckets and M colored balls to put in them, find the earliest moment when some bucket contains Q balls of the same color.
Task Score
100%
Correctness
100%
Performance
100%
There are N buckets numbered from 0 to N−1. There are also M balls of different colors, numbered from 0 to M−1. The K-th ball has color C[K]. For simplicity we denote each color by an integer.
Initially all buckets are empty. At moment K (for K from 0 to M−1), we put the K-th ball into bucket B[K].
Calculate the earliest moment when there are at least Q balls of the same color in some bucket.
Write a function:
int solution(int N, int Q, vector<int> &B, vector<int> &C);
that, given two integers N and Q, and two arrays B and C consisting of M integers each, returns the earliest moment in which there is some bucket with at least Q balls of the same color. The function should return −1 if no such moment occurs.
Examples:
1. Given N = 3, Q = 2, B = [1, 2, 0, 1, 1, 0, 0, 1] and C = [0, 3, 0, 2, 0, 3, 0, 0], the function should return 4. At moment 3 we have a ball of color 0 in bucket 0, balls of colors 0 and 2 in bucket 1, and a ball of color 3 in bucket 2. At moment 4 we put another ball of color 0 into bucket 1, and there are thus two balls of the same color in this bucket.
2. Given N = 2, Q = 2, B = [0, 1] and C = [5, 5], the function should return −1. There is no moment in which there is some bucket with at least 2 balls of the same color.
3. Given N = 2, Q = 2, B = [0, 1, 0, 1, 0, 1] and C = [1, 3, 0, 0, 3, 3], the function should return 5.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..1,000,000];
- Q and M are integers within the range [1..100,000];
- each element of array B is an integer within the range [0..N-1];
- each element of array C is an integer within the range [0..1,000,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 19 minutes
Notes
not defined yet
Code: 11:33:22 UTC,
java,
autosave
Code: 11:34:01 UTC,
cpp,
autosave
Code: 11:34:46 UTC,
cpp,
autosave
Code: 11:40:21 UTC,
cpp,
autosave
Code: 11:40:39 UTC,
cpp,
autosave
Code: 11:41:10 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include map:
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++B){
}
}
Code: 11:41:20 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++B){
}
}
Code: 11:41:51 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++B){
M[{}]
}
}
Code: 11:42:11 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++B){
pair<int, int> p = {}
}
}
Code: 11:42:27 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], }
}
}
Code: 11:42:48 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q)
}
}
Code: 11:43:03 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
}
Code: 11:43:56 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
}
Code: 11:43:59 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <pair>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
return -1;
}
Analysis
Compile error
func.cpp:3:16: fatal error: pair: No such file or directory
#include <pair>
^
compilation terminated.
Code: 11:44:19 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <bit/stdc++.h>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
return -1;
}
Analysis
Compile error
func.cpp:3:24: fatal error: bit/stdc++.h: No such file or directory
#include <bit/stdc++.h>
^
compilation terminated.
Code: 11:44:26 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <pairs>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
return -1;
}
Code: 11:44:28 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <pairs>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
return -1;
}
Analysis
Compile error
func.cpp:3:17: fatal error: pairs: No such file or directory
#include <pairs>
^
compilation terminated.
Code: 11:44:54 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <std>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
return -1;
}
Analysis
Compile error
func.cpp:3:15: fatal error: std: No such file or directory
#include <std>
^
compilation terminated.
Code: 11:46:20 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
return -1;
}
Code: 11:46:21 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == q) return i + 1;
}
return -1;
}
Analysis
Compile error
func.cpp: In function 'int solution(int, int, std::vector<int>&, std::vector<int>&)':
func.cpp:11:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < B.size(); ++i){
~~^~~~~~~~~~
func.cpp:14:19: error: 'q' was not declared in this scope
if(M[p] == q) return i + 1;
^
Code: 11:46:35 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return i + 1;
}
return -1;
}
Analysis
expand all
Example tests
1.
0.001 s
WRONG ANSWER,
got 5 expected 4
1.
0.001 s
OK
1.
0.001 s
WRONG ANSWER,
got 6 expected 5
Code: 11:49:44 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return i + 1;
}
return -1;
}
Code: 11:49:56 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return i + 1;
}
return -1;
}
Code: 11:50:06 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return i + 1;
}
return -1;
}
Analysis
expand all
Example tests
1.
0.001 s
WRONG ANSWER,
got 5 expected 4
1.
0.001 s
OK
1.
0.001 s
WRONG ANSWER,
got 6 expected 5
Code: 11:50:49 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return C[];
}
return -1;
}
Code: 11:50:51 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return C[i];
}
return -1;
}
Analysis
expand all
Example tests
1.
0.001 s
WRONG ANSWER,
got 0 expected 4
1.
0.001 s
OK
1.
0.001 s
WRONG ANSWER,
got 3 expected 5
Code: 11:51:17 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return i;
}
return -1;
}
Analysis
Code: 11:51:22 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return i;
}
return -1;
}
Analysis
Code: 11:51:26 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return i;
}
return -1;
}
Analysis
Code: 11:51:30 UTC,
cpp,
final,
score:
100
// you can use includes, for example:
#include <algorithm>
#include <utility>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(int N, int Q, vector<int> &B, vector<int> &C) {
map<pair<int, int>, int> M;
for(int i = 0; i < B.size(); ++i){
pair<int, int> p = {B[i], C[i]};
M[p]++;
if(M[p] == Q) return i;
}
return -1;
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M*log(M))
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
expand all
Correctness/performance tests
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.036 s
OK
4.
0.008 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.036 s
OK
4.
0.008 s
OK
1.
0.032 s
OK
2.
0.052 s
OK
3.
0.064 s
OK
1.
0.032 s
OK
2.
0.048 s
OK
3.
0.064 s
OK