Tasks Details
medium
Find the smallest positive integer that does not occur in a given sequence.
Task Score
88%
Correctness
100%
Performance
75%
This is a demo task.
Write a function:
class Solution { public int solution(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–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 26 minutes
Notes
not defined yet
Code: 11:25:34 UTC,
java,
verify,
result: Failed
Analysis
Compile error
Solution.java:7: error: cannot find symbol
A = A.sort(A);
^
symbol: method sort(int[])
location: variable A of type int[]
1 error
Code: 11:26:00 UTC,
java,
verify,
result: Failed
Analysis
Compile error
Solution.java:7: error: incompatible types: void cannot be converted to int[]
A = Arrays.sort(A);
^
1 error
Code: 11:27:00 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
class Solution
{
public int solution(int[] A)
{
Arrays.sort(A);
int next = 1;
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2]
User test case 3:
[1, 2, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
Example tests
1.
0.909 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:12) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
expand all
User tests
1.
0.902 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2 at Solution.solution(Solution.java:12) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
1.
0.949 s
OK
function result: 1
function result: 1
1.
0.969 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:12) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
1.
0.902 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -4 at Solution.solution(Solution.java:12) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 11:28:51 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
class Solution
{
public int solution(int[] A)
{
Arrays.sort(A);
int next = 1;
System.out.println(Arrays.binarySearch(A, 0));
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2]
User test case 3:
[1, 2, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
Example tests
1.
1.353 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
-1
expand all
User tests
1.
1.350 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
-2
1.
1.341 s
OK
function result: 1
function result: 1
stdout:
1
1.
1.351 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
-1
1.
1.347 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -4 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
-4
Code: 11:29:51 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
class Solution
{
public int solution(int[] A)
{
Arrays.sort(A);
int next = 1;
System.out.println(Arrays.toString(A));
System.out.println(Arrays.binarySearch(A, 0));
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2]
User test case 3:
[1, 2, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
Example tests
1.
1.437 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:15) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1, 1, 2, 3, 4, 6] -1
expand all
User tests
1.
1.438 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2 at Solution.solution(Solution.java:15) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[-1, 1] -2
1.
1.450 s
OK
function result: 1
function result: 1
stdout:
[-2, 0] 1
1.
1.428 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:15) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1, 2, 4] -1
1.
1.439 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -4 at Solution.solution(Solution.java:15) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[-5, -3, -2, 4] -4
Code: 11:33:26 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> return s > 0 ).toArray();
System.out.println( Arrays.(a) );
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
Analysis
Compile error
Solution.java:7: error: illegal start of expression
int[] a = IntStream.of(A).distinct().filter( s -> return s > 0 ).toArray();
^
Solution.java:7: error: ';' expected
int[] a = IntStream.of(A).distinct().filter( s -> return s > 0 ).toArray();
^
Solution.java:7: error: illegal start of expression
int[] a = IntStream.of(A).distinct().filter( s -> return s > 0 ).toArray();
^
Solution.java:7: error: ';' expected
int[] a = IntStream.of(A).distinct().filter( s -> return s > 0 ).toArray();
^
Solution.java:7: error: illegal start of expression
int[] a = IntStream.of(A).distinct().filter( s -> return s > 0 ).toArray();
^
Solution.java:7: error: ';' expected
int[] a = IntStream.of(A).distinct().filter( s -> return s > 0 ).toArray();
^
Solution.java:9: error: <identifier> expected
System.out.println( Arrays.(a) );
^
7 errors
Code: 11:33:37 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
System.out.println( Arrays.(a) );
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
Analysis
Compile error
Solution.java:9: error: <identifier> expected
System.out.println( Arrays.(a) );
^
1 error
Code: 11:33:51 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
System.out.println( Arrays.toString(a) );
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
Analysis
Compile error
Solution.java:7: error: cannot find symbol
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
^
symbol: variable IntStream
location: class Solution
Solution.java:13: error: cannot find symbol
if( A[i] == next )
^
symbol: variable next
location: class Solution
Solution.java:14: error: cannot find symbol
next++;
^
symbol: variable next
location: class Solution
Solution.java:15: error: cannot find symbol
else if (A[i] > next)
^
symbol: variable next
location: class Solution
Solution.java:16: error: cannot find symbol
return next;
^
symbol: variable next
location: class Solution
Solution.java:19: error: cannot find symbol
return next;
^
symbol: variable next
location: class Solution
6 errors
Code: 11:34:10 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
System.out.println( Arrays.toString(a) );
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
Analysis
Compile error
Solution.java:14: error: cannot find symbol
if( A[i] == next )
^
symbol: variable next
location: class Solution
Solution.java:15: error: cannot find symbol
next++;
^
symbol: variable next
location: class Solution
Solution.java:16: error: cannot find symbol
else if (A[i] > next)
^
symbol: variable next
location: class Solution
Solution.java:17: error: cannot find symbol
return next;
^
symbol: variable next
location: class Solution
Solution.java:20: error: cannot find symbol
return next;
^
symbol: variable next
location: class Solution
5 errors
Code: 11:34:24 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
int next = 1;
System.out.println( Arrays.toString(a) );
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2]
User test case 3:
[1, 2, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
Example tests
1.
1.714 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1, 3, 6, 4, 2]
expand all
User tests
1.
1.608 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1]
1.
1.581 s
OK
function result: 1
function result: 1
stdout:
[]
1.
1.623 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1, 2, 4]
1.
1.634 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -4 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[4]
Code: 11:35:01 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
int next = 1;
System.out.println( Arrays.toString(a) );
for (int i = Arrays.binarySearch(A, 0); i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2, 1, -2]
User test case 3:
[1, 2, 4, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
Example tests
1.
1.984 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1, 3, 6, 4, 2]
expand all
User tests
1.
1.985 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1]
1.
1.993 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -3 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1]
1.
1.938 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[1, 2, 4]
1.
1.590 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -4 at Solution.solution(Solution.java:14) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)stdout:
[4]
Code: 11:36:20 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
Arrays.sort(a);
int next = 1;
for (int i = 0; i < A.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2, 1, -2]
User test case 3:
[1, 2, 4, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
Example tests
1.
1.628 s
WRONG ANSWER,
got 2 expected 5
expand all
User tests
1.
1.574 s
OK
function result: 2
function result: 2
1.
1.520 s
OK
function result: 2
function result: 2
1.
1.529 s
OK
function result: 3
function result: 3
1.
1.542 s
OK
function result: 1
function result: 1
Code: 11:37:21 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
Arrays.sort(a);
int next = 1;
for (int i = 0; i < a.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2, 1, -2]
User test case 3:
[1, 2, 4, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
Example tests
1.
1.527 s
WRONG ANSWER,
got 2 expected 5
expand all
User tests
1.
1.375 s
OK
function result: 2
function result: 2
1.
1.339 s
OK
function result: 1
function result: 1
1.
1.339 s
OK
function result: 3
function result: 3
1.
1.342 s
OK
function result: 1
function result: 1
Code: 11:37:52 UTC,
java,
verify,
result: Failed
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
Arrays.sort(a);
int next = 1;
System.out.println(Arrays.toString(a));
for (int i = 0; i < a.length; i++ )
{
if( A[i] == next )
next++;
else if (A[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2, 1, -2]
User test case 3:
[1, 2, 4, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
Example tests
1.
1.583 s
WRONG ANSWER,
got 2 expected 5
stdout:
[1, 2, 3, 4, 6]
expand all
User tests
1.
1.606 s
OK
function result: 2
function result: 2
stdout:
[1]
1.
1.665 s
OK
function result: 1
function result: 1
stdout:
[1]
1.
1.613 s
OK
function result: 3
function result: 3
stdout:
[1, 2, 4]
1.
1.556 s
OK
function result: 1
function result: 1
stdout:
[4]
Code: 11:38:27 UTC,
java,
verify,
result: Passed
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
Arrays.sort(a);
int next = 1;
for (int i = 0; i < a.length; i++ )
{
if( a[i] == next )
next++;
else if (a[i] > next)
return next;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2, 1, -2]
User test case 3:
[1, 2, 4, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
User tests
1.
1.965 s
OK
function result: 2
function result: 2
1.
1.964 s
OK
function result: 2
function result: 2
1.
1.970 s
OK
function result: 3
function result: 3
1.
1.977 s
OK
function result: 1
function result: 1
Code: 11:39:24 UTC,
java,
verify,
result: Passed
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
Arrays.sort(a);
int next = 1;
for (int i = 0; i < a.length; i++ )
{
if( a[i] == next )
next++;
else if ( a[i] > next)
break;
}
return next;
}
}
User test case 1:
[1, -1]
User test case 2:
[0, -2, 1, -2]
User test case 3:
[1, 2, 4, 4]
User test case 4:
[-5, -2, -3, 4]
Analysis
expand all
User tests
1.
1.361 s
OK
function result: 2
function result: 2
1.
1.781 s
OK
function result: 2
function result: 2
1.
1.940 s
OK
function result: 3
function result: 3
1.
1.956 s
OK
function result: 1
function result: 1
Code: 11:39:36 UTC,
java,
final,
score:
88
import java.util.Arrays;
import java.util.stream.*;
class Solution
{
public int solution(int[] A)
{
int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
Arrays.sort(a);
int next = 1;
for (int i = 0; i < a.length; i++ )
{
if( a[i] == next )
next++;
else if ( a[i] > next)
break;
}
return next;
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
1.966 s
OK
2.
1.955 s
OK
3.
1.966 s
OK
1.
1.938 s
OK
2.
1.708 s
OK
1.
1.961 s
OK
2.
1.961 s
OK
1.
1.946 s
OK
1.
1.961 s
OK
expand all
Performance tests
medium
chaotic sequences length=10005 (with minus)
chaotic sequences length=10005 (with minus)
✘
TIMEOUT ERROR
running time: 1.93 sec., time limit: 1.50 sec.
running time: 1.93 sec., time limit: 1.50 sec.
1.
1.950 s
OK
2.
1.929 s
TIMEOUT ERROR,
running time: 1.93 sec., time limit: 1.50 sec.
3.
2.031 s
OK
1.
2.482 s
OK
1.
2.643 s
OK
2.
2.636 s
OK
1.
2.304 s
OK