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 3 minutes
Effective time used 3 minutes
Notes
not defined yet
Task timeline
Code: 08:50:05 UTC,
java,
autosave
Code: 08:50:20 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, A):
M = len(A)
count = [0]*(N + 1)
max_counter = 0
offset = 0
for k in range(M):
# max counter operation, defines a offset with the value of the max counter of the count array at the time
if A[k] > N:
offset = max_counter
# increase(x) operation, id a max counter operation happened updates the count of the element A[k] accordingly
else:
count[A[k]] = max(offset + 1, count[A[k]] + 1)
# Tracks the max counter value of the count array
if max_counter < count[A[k]]:
max_counter = count[A[k]]
# Updates the values that were not updated before by the max counter operation
for k in range(1, N + 1):
if count[k] < offset:
count[k] = offset
return count[1:]
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 91, in main result = solution( A ) TypeError: solution() missing 1 required positional argument: 'A'
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 91, in main result = solution( A ) TypeError: solution() missing 1 required positional argument: 'A'
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 91, in main result = solution( A ) TypeError: solution() missing 1 required positional argument: 'A'
Code: 08:50:42 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
M = len(A)
count = [0]*(N + 1)
max_counter = 0
offset = 0
for k in range(M):
# max counter operation, defines a offset with the value of the max counter of the count array at the time
if A[k] > N:
offset = max_counter
# increase(x) operation, id a max counter operation happened updates the count of the element A[k] accordingly
else:
count[A[k]] = max(offset + 1, count[A[k]] + 1)
# Tracks the max counter value of the count array
if max_counter < count[A[k]]:
max_counter = count[A[k]]
# Updates the values that were not updated before by the max counter operation
for k in range(1, N + 1):
if count[k] < offset:
count[k] = offset
return count[1:]
Code: 08:50:44 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
M = len(A)
count = [0]*(N + 1)
max_counter = 0
offset = 0
for k in range(M):
# max counter operation, defines a offset with the value of the max counter of the count array at the time
if A[k] > N:
offset = max_counter
# increase(x) operation, id a max counter operation happened updates the count of the element A[k] accordingly
else:
count[A[k]] = max(offset + 1, count[A[k]] + 1)
# Tracks the max counter value of the count array
if max_counter < count[A[k]]:
max_counter = count[A[k]]
# Updates the values that were not updated before by the max counter operation
for k in range(1, N + 1):
if count[k] < offset:
count[k] = offset
return count[1:]
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 91, in main result = solution( A ) File "/tmp/solution.py", line 6, in solution count = [0]*(N + 1) NameError: name 'N' is not defined
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 91, in main result = solution( A ) File "/tmp/solution.py", line 6, in solution count = [0]*(N + 1) NameError: name 'N' is not defined
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 91, in main result = solution( A ) File "/tmp/solution.py", line 6, in solution count = [0]*(N + 1) NameError: name 'N' is not defined
Code: 08:51:51 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
count = [0]*(N + 1)
# Counts all elements of A tha belongs to sequence {1, ..., N}
for k in xrange(N):
if N >= A[k] > 0:
count[A[k]] += 1
# Searches for the lesser integer that not belongs to A
for k in xrange(1, N + 1):
if count[k] == 0:
return k
# If A has all elements from 1 to N, N + 1 is the minimal integer
return N + 1
Code: 08:51:55 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
count = [0]*(N + 1)
# Counts all elements of A tha belongs to sequence {1, ..., N}
for k in range(N):
if N >= A[k] > 0:
count[A[k]] += 1
# Searches for the lesser integer that not belongs to A
for k in range(1, N + 1):
if count[k] == 0:
return k
# If A has all elements from 1 to N, N + 1 is the minimal integer
return N + 1
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 70, in main sol = __import__('solution') File "/tmp/solution.py", line 10 if N >= A[k] > 0: ^ TabError: inconsistent use of tabs and spaces in indentation
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 70, in main sol = __import__('solution') File "/tmp/solution.py", line 10 if N >= A[k] > 0: ^ TabError: inconsistent use of tabs and spaces in indentation
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 70, in main sol = __import__('solution') File "/tmp/solution.py", line 10 if N >= A[k] > 0: ^ TabError: inconsistent use of tabs and spaces in indentation
Code: 08:52:13 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
count = [0]*(N + 1)
# Counts all elements of A tha belongs to sequence {1, ..., N}
for k in range(N):
if N >= A[k] > 0:
count[A[k]] += 1
# Searches for the lesser integer that not belongs to A
for k in range(1, N + 1):
if count[k] == 0:
return k
# If A has all elements from 1 to N, N + 1 is the minimal integer
return N + 1
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 70, in main sol = __import__('solution') File "/tmp/solution.py", line 10 if N >= A[k] > 0: ^ IndentationError: expected an indented block
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 70, in main sol = __import__('solution') File "/tmp/solution.py", line 10 if N >= A[k] > 0: ^ IndentationError: expected an indented block
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 70, in main sol = __import__('solution') File "/tmp/solution.py", line 10 if N >= A[k] > 0: ^ IndentationError: expected an indented block
Code: 08:52:19 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
count = [0]*(N + 1)
# Counts all elements of A tha belongs to sequence {1, ..., N}
for k in range(N):
if N >= A[k] > 0:
count[A[k]] += 1
# Searches for the lesser integer that not belongs to A
for k in range(1, N + 1):
if count[k] == 0:
return k
# If A has all elements from 1 to N, N + 1 is the minimal integer
return N + 1
Analysis
Code: 08:52:28 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
count = [0]*(N + 1)
# Counts all elements of A tha belongs to sequence {1, ..., N}
for k in range(N):
if N >= A[k] > 0:
count[A[k]] += 1
# Searches for the lesser integer that not belongs to A
for k in range(1, N + 1):
if count[k] == 0:
return k
# If A has all elements from 1 to N, N + 1 is the minimal integer
return N + 1
Analysis
Code: 08:52:30 UTC,
py,
final,
score: 
100
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
count = [0]*(N + 1)
# Counts all elements of A tha belongs to sequence {1, ..., N}
for k in range(N):
if N >= A[k] > 0:
count[A[k]] += 1
# Searches for the lesser integer that not belongs to A
for k in range(1, N + 1):
if count[k] == 0:
return k
# If A has all elements from 1 to N, N + 1 is the minimal integer
return N + 1
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N) or O(N * log(N))
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
expand all
Performance tests
1.
0.044 s
OK
2.
0.044 s
OK
3.
0.044 s
OK
1.
0.140 s
OK
1.
0.156 s
OK
2.
0.152 s
OK
1.
0.148 s
OK