Tasks Details
medium
Find the smallest positive integer that does not occur in a given sequence.
Task Score
22%
Correctness
20%
Performance
25%
This is a demo task.
Write a function:
def 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 Python
Time spent on task 1 minutes
Notes
not defined yet
Task timeline
Code: 13:24:59 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
if len(A) < 2:
return 0
minN = 2147483647
maxN = -2147483648
for i in A:
if i > maxN:
maxN = i
if i < minN:
minN = i
T = [0] * (maxN - minN + 1)
for i in A:
T[i - minN] += 1
for j in range(len(T)):
if T[j] == 0:
return minN + j
return 0
pass
Analysis
Code: 13:25:03 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
if len(A) < 2:
return 0
minN = 2147483647
maxN = -2147483648
for i in A:
if i > maxN:
maxN = i
if i < minN:
minN = i
T = [0] * (maxN - minN + 1)
for i in A:
T[i - minN] += 1
for j in range(len(T)):
if T[j] == 0:
return minN + j
return 0
pass
Analysis
Code: 13:25:06 UTC,
py,
final,
score:
22
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
if len(A) < 2:
return 0
minN = 2147483647
maxN = -2147483648
for i in A:
if i > maxN:
maxN = i
if i < minN:
minN = i
T = [0] * (maxN - minN + 1)
for i in A:
T[i - minN] += 1
for j in range(len(T)):
if T[j] == 0:
return minN + j
return 0
passAnalysis summary
The following issues have been detected: wrong answers, runtime errors.
For example, for the input [1] the solution returned a wrong answer (got 0 expected 2).
Analysis
expand all
Correctness tests
1.
0.058 s
WRONG ANSWER,
got 0 expected 2
2.
0.058 s
WRONG ANSWER,
got 0 expected 1
3.
0.057 s
WRONG ANSWER,
got 0 expected 1
1.
0.057 s
WRONG ANSWER,
got 3 expected 1
2.
0.057 s
OK
extreme_min_max_int
MININT and MAXINT (with minus)
MININT and MAXINT (with minus)
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.059 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 109, in <module>
main()
File "user.py", line 86, in main
result = sol.solution ( A )
File "/tmp/solution.py", line 19, in solution
T = [0] * (maxN - minN + 1)
MemoryError
2.
0.059 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 109, in <module>
main()
File "user.py", line 86, in main
result = sol.solution ( A )
File "/tmp/solution.py", line 19, in solution
T = [0] * (maxN - minN + 1)
MemoryError
1.
0.058 s
OK
1.
0.057 s
WRONG ANSWER,
got 0 expected 1
expand all
Performance tests
1.
0.068 s
WRONG ANSWER,
got -965 expected 111
2.
0.066 s
WRONG ANSWER,
got 0 expected 101
3.
0.070 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 109, in <module>
main()
File "user.py", line 86, in main
result = sol.solution ( A )
File "/tmp/solution.py", line 19, in solution
T = [0] * (maxN - minN + 1)
MemoryError
1.
0.150 s
OK
1.
0.160 s
WRONG ANSWER,
got 0 expected 100001
2.
0.160 s
OK
large_3
chaotic + many -1, 1, 2, 3 (with minus)
chaotic + many -1, 1, 2, 3 (with minus)
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.141 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 109, in <module>
main()
File "user.py", line 86, in main
result = sol.solution ( A )
File "/tmp/solution.py", line 19, in solution
T = [0] * (maxN - minN + 1)
MemoryError