Tasks Details
medium
Find the smallest positive integer that does not occur in a given sequence.
Task Score
100%
Correctness
100%
Performance
100%
This is a demo task.
Write a function:
int solution(vector<int> &A);
that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [−1,000,000..1,000,000].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Total time used 10 minutes
Effective time used 10 minutes
Notes
not defined yet
Task timeline
Code: 14:59:07 UTC,
java,
autosave
Code: 14:59:11 UTC,
cpp,
autosave
Code: 14:59:19 UTC,
cpp,
autosave
Code: 14:59:49 UTC,
cpp,
autosave
Code: 15:00:07 UTC,
cpp,
autosave
Code: 15:00:37 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negativbe(1000000,false);
std::vector<bool> non_negativbe(1000000,false);
for(int a : A){
}
}
Code: 15:00:47 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negativbe(1000000,false);
std::vector<bool> non_negativbe(1000000,false);
for(int a : A){
if(a<0)
}
}
Code: 15:01:17 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negativbe(1000000,false);
std::vector<bool> non_negativbe(1000000,false);
for(int a : A){
if(a<0) {
negative[-a]=true;
} else {
}
}
}
Code: 15:01:36 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negativbe(1000000,false);
std::vector<bool> non_negativbe(1000000,false);
for(int a : A){
if(a<0) {
negative[-a]=true;
} else {
non_negative[a]=true;
}
}
}
Code: 15:01:59 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000,false);
for(int a : A){
if(a<0) {
negative[-a]=true;
} else {
non_negative[a]=true;
}
}
}
Code: 15:02:18 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
for(int a : A){
if(a<0) {
negative[-a]=true;
} else {
non_negative[a]=true;
}
}
}
Code: 15:02:48 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative
for(int a : A){
if(a<0) {
negative[-a]=true;
} else {
non_negative[a]=true;
}
}
}
Code: 15:03:18 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
}
Code: 15:03:48 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
if(contain_negative && !contain_positive){
return 1;
} else {
return 5;
}
}
Code: 15:03:50 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
if(contain_negative && !contain_positive){
return 1;
} else {
return 5;
}
}
Analysis
Compile error
func.cpp: In function 'int solution(std::vector<int>&)': func.cpp:22:29: error: 'contain_positive' was not declared in this scope if(contain_negative && !contain_positive){ ^~~~~~~~~~~~~~~~ func.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type] } ^
Code: 15:04:05 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
if(contain_negative && !contain_positive){
return 1;
} else {
return 5;
}
return 5;
}
Analysis
Compile error
func.cpp: In function 'int solution(std::vector<int>&)': func.cpp:22:29: error: 'contain_positive' was not declared in this scope if(contain_negative && !contain_positive){ ^~~~~~~~~~~~~~~~
Code: 15:04:21 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
if(contain_negative && !contain_non_negative){
return 1;
} else {
return 5;
}
return 5;
}
Code: 15:04:23 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
if(contain_negative && !contain_non_negative){
return 1;
} else {
return 5;
}
return 5;
}
Analysis
Code: 15:04:51 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
if(contain_negative && !contain_non_negative){
return 1;
} else {
for(size_t i )
}
return 5;
}
Code: 15:05:16 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
if(contain_negative && !contain_non_negative){
return 1;
} else {
for(size_t i = 0; i < non_negative.size(); i++){
}
}
return 5;
}
Code: 15:05:33 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result =
if(contain_negative && !contain_non_negative){
return 1;
} else {
for(size_t i = 0; i < non_negative.size(); i++){
}
}
return 5;
}
Code: 15:05:46 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 0; i < non_negative.size(); i++){
}
}
return 5;
}
Code: 15:05:56 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 0; i < non_negative.size(); i++){
}
}
return result;
}
Code: 15:06:27 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
}
}
return result;
}
Code: 15:06:37 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
if
}
}
return result;
}
Code: 15:06:53 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
if(non_negative[i])
}
}
return result;
}
Code: 15:07:12 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
if(non_negative[i]){
result = i;
break;
}
}
}
return result;
}
Analysis
expand all
Example tests
1.
0.001 s
WRONG ANSWER,
got 1 expected 5
1.
0.001 s
WRONG ANSWER,
got 1 expected 4
1.
0.001 s
OK
Code: 15:07:31 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
if(!non_negative[i]){
result = i;
break;
}
}
}
return result;
}
Code: 15:07:33 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
if(!non_negative[i]){
result = i;
break;
}
}
}
return result;
}
Analysis
Code: 15:08:12 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
if(!non_negative[i]){
result = i;
break;
}
}
}
return result;
}
Analysis
Code: 15:08:15 UTC,
cpp,
final,
score: 
100
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
if(!non_negative[i]){
result = i;
break;
}
}
}
return result;
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N) or O(N * log(N))
expand all
Correctness tests
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
3.
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
expand all
Performance tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.004 s
OK