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:
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
Total time used 4 minutes
Effective time used 4 minutes
Notes
not defined yet
Task timeline
Code: 04:51:43 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
N = len(A)
C = [0] * N
res = 0
for i in A:
if i > 0 and i <= N:
C[i-1] += 1
for i in range(1, N+1):
if not C[i-1]:
res = i
if not res: res = N + 1
return res
User test case 1:
[1, 2, 3, 4, 5]
User test case 2:
[-2, 500, 1, 13]
User test case 3:
[0, 0, 0, 0, 0]
Analysis
expand all
User tests
1.
0.067 s
OK
function result: 6
function result: 6
1.
0.071 s
OK
function result: 4
function result: 4
1.
0.072 s
OK
function result: 5
function result: 5
Code: 04:52:10 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
N = len(A)
C = [0] * N
res = 0
for i in A:
if i > 0 and i <= N:
C[i-1] += 1
for i in range(1, N+1):
if not C[i-1]:
res = i
break
if not res: res = N + 1
return res
User test case 1:
[1, 2, 3, 4, 5]
User test case 2:
[-2, 500, 1, 13]
User test case 3:
[0, 0, 0, 0, 0]
Analysis
expand all
User tests
1.
0.069 s
OK
function result: 6
function result: 6
1.
0.069 s
OK
function result: 2
function result: 2
1.
0.068 s
OK
function result: 1
function result: 1
Code: 04:52:23 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
N = len(A)
C = [0] * N
res = 0
for i in A:
if i > 0 and i <= N:
C[i-1] += 1
for i in range(1, N+1):
if not C[i-1]:
res = i
break
if not res: res = N + 1
return res
User test case 1:
[1, 2, 3, 4, 5]
User test case 2:
[-2, 500, 1, 13]
User test case 3:
[0, 0, 0, 0, 0]
User test case 4:
[1]
Analysis
expand all
User tests
1.
0.068 s
OK
function result: 6
function result: 6
1.
0.072 s
OK
function result: 2
function result: 2
1.
0.072 s
OK
function result: 1
function result: 1
1.
0.068 s
OK
function result: 2
function result: 2
Code: 04:52:36 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
N = len(A)
C = [0] * N
res = 0
for i in A:
if i > 0 and i <= N:
C[i-1] += 1
for i in range(1, N+1):
if not C[i-1]:
res = i
break
if not res: res = N + 1
return res
User test case 1:
[1, 2, 3, 4, 5]
User test case 2:
[-2, 500, 1, 13]
User test case 3:
[0, 0, 0, 0, 0]
User test case 4:
[1]
Analysis
expand all
User tests
1.
0.071 s
OK
function result: 6
function result: 6
1.
0.072 s
OK
function result: 2
function result: 2
1.
0.071 s
OK
function result: 1
function result: 1
1.
0.073 s
OK
function result: 2
function result: 2
Code: 04:52:38 UTC,
py,
final,
score: 
100
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
N = len(A)
C = [0] * N
res = 0
for i in A:
if i > 0 and i <= N:
C[i-1] += 1
for i in range(1, N+1):
if not C[i-1]:
res = i
break
if not res: res = N + 1
return res
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.067 s
OK
2.
0.068 s
OK
3.
0.064 s
OK
1.
0.068 s
OK
2.
0.068 s
OK
1.
0.066 s
OK
2.
0.065 s
OK
1.
0.068 s
OK
1.
0.064 s
OK
expand all
Performance tests
1.
0.079 s
OK
2.
0.076 s
OK
3.
0.083 s
OK
1.
0.152 s
OK
1.
0.170 s
OK
2.
0.167 s
OK
1.
0.151 s
OK