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:
function solution($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 PHP
Total time used 1 minutes
Effective time used 1 minutes
Notes
not defined yet
Task timeline
Code: 10:35:25 UTC,
php,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($A){
$A = array_unique($A);
sort($A);
if (empty($A)) return 1;
if (max($A) <= 0) return 1;
if (max($A) == 1) return 2;
if (in_array(1, $A)) { // postoji 1, ali 1 nije max
$A = array_slice($A, array_search(1, $A)); // from 0 to the end
array_unshift($A, 0);
// return $A;
if ( max($A) == array_search(max($A), $A)) return max($A) + 1; // increasing array, if the last element is the max
// $result = intval(ceil((count($A)+1) * (count($A)+2) / 2 - array_sum($A)));
for ($i = 1; $i <= count($A); $i++){ // za nizove
if ($A[$i] != $i) return $i;
}
// return $result;
} else { // ne postoji 1
return 1;
}
}
Analysis
Code: 10:35:29 UTC,
php,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($A){
$A = array_unique($A);
sort($A);
if (empty($A)) return 1;
if (max($A) <= 0) return 1;
if (max($A) == 1) return 2;
if (in_array(1, $A)) { // postoji 1, ali 1 nije max
$A = array_slice($A, array_search(1, $A)); // from 0 to the end
array_unshift($A, 0);
// return $A;
if ( max($A) == array_search(max($A), $A)) return max($A) + 1; // increasing array, if the last element is the max
// $result = intval(ceil((count($A)+1) * (count($A)+2) / 2 - array_sum($A)));
for ($i = 1; $i <= count($A); $i++){ // za nizove
if ($A[$i] != $i) return $i;
}
// return $result;
} else { // ne postoji 1
return 1;
}
}
Analysis
Code: 10:35:32 UTC,
php,
final,
score: 
100
// you can write to stdout for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($A){
$A = array_unique($A);
sort($A);
if (empty($A)) return 1;
if (max($A) <= 0) return 1;
if (max($A) == 1) return 2;
if (in_array(1, $A)) { // postoji 1, ali 1 nije max
$A = array_slice($A, array_search(1, $A)); // from 0 to the end
array_unshift($A, 0);
// return $A;
if ( max($A) == array_search(max($A), $A)) return max($A) + 1; // increasing array, if the last element is the max
// $result = intval(ceil((count($A)+1) * (count($A)+2) / 2 - array_sum($A)));
for ($i = 1; $i <= count($A); $i++){ // za nizove
if ($A[$i] != $i) return $i;
}
// return $result;
} else { // ne postoji 1
return 1;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.024 s
OK
2.
0.025 s
OK
3.
0.024 s
OK
1.
0.024 s
OK
2.
0.024 s
OK
1.
0.024 s
OK
2.
0.024 s
OK
1.
0.025 s
OK
1.
0.025 s
OK
expand all
Performance tests
1.
0.060 s
OK
2.
0.057 s
OK
3.
0.072 s
OK
1.
0.500 s
OK
1.
0.605 s
OK
2.
0.630 s
OK
1.
0.429 s
OK