Tasks Details
easy
1.
PermCheck
Check whether array A is a permutation.
Task Score
100%
Correctness
100%
Performance
100%
A non-empty array A consisting of N integers is given.
A permutation is a sequence containing each element from 1 to N once, and only once.
For example, array A such that:
A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2is a permutation, but array A such that:
A[0] = 4 A[1] = 1 A[2] = 3is not a permutation, because value 2 is missing.
The goal is to check whether array A is a permutation.
Write a function:
def solution(A)
that, given an array A, returns 1 if array A is a permutation and 0 if it is not.
For example, given array A such that:
A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2the function should return 1.
Given array A such that:
A[0] = 4 A[1] = 1 A[2] = 3the function should return 0.
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..1,000,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 7 minutes
Effective time used 7 minutes
Notes
not defined yet
Task timeline
Code: 05:52:07 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 = N
result = 1
A_ = [0] * N
for i in A:
if i > N:
result = 0
break
elif not A_[i]:
A_[i] = 1
count -= 1
if count:
result = 0
return result
Analysis
expand all
Example tests
1.
0.073 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 16, in solution elif not A_[i]: IndexError: list index out of range
1.
0.065 s
OK
Code: 05:53:04 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 = N
result = 1
A_ = [0] * N+1
for i in A:
if i > N:
result = 0
break
elif i <= N and not A_[i]:
A_[i] = 1
count -= 1
if count:
result = 0
return result
Analysis
expand all
Example tests
1.
0.068 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 10, in solution A_ = [0] * N+1 TypeError: can only concatenate list (not "int") to list
1.
0.073 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 10, in solution A_ = [0] * N+1 TypeError: can only concatenate list (not "int") to list
Code: 05:53:46 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 = N
result = 1
A_ = [0] * N
for i in A:
if i > N:
result = 0
break
elif i <= N and not A_[i-1]:
A_[i-1] = 1
count -= 1
if count:
result = 0
return result
Analysis
Code: 05:55:27 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)
if not N: return 0
count = N
result = 1
A_ = [0] * N
for i in A:
if i > N:
result = 0
break
elif i <= N and not A_[i-1]:
A_[i-1] = 1
count -= 1
if count:
result = 0
return result
Analysis
Code: 05:55:52 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)
if not N: return 0
count = N
result = 1
A_ = [0] * N
for i in A:
if i > N:
result = 0
break
elif i <= N and not A_[i-1]:
A_[i-1] = 1
count -= 1
if count:
result = 0
return result
User test case 1:
[]
User test case 2:
[1, 2, 1, 1, 1, 3]
User test case 3:
[1, 2, 3, 4]
Analysis
expand all
User tests
1.
0.032 s
OK
function result: 0
function result: 0
1.
0.031 s
OK
function result: 0
function result: 0
1.
0.031 s
OK
function result: 1
function result: 1
Code: 05:56:11 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)
if not N: return 0
count = N
result = 1
A_ = [0] * N
for i in A:
if i > N:
result = 0
break
elif i <= N and not A_[i-1]:
A_[i-1] = 1
count -= 1
if count:
result = 0
return result
User test case 1:
[]
User test case 2:
[1, 2, 1, 1, 1, 3]
User test case 3:
[1, 2, 3, 4]
Analysis
expand all
User tests
1.
0.071 s
OK
function result: 0
function result: 0
1.
0.071 s
OK
function result: 0
function result: 0
1.
0.069 s
OK
function result: 1
function result: 1
Code: 05:56:13 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)
if not N: return 0
count = N
result = 1
A_ = [0] * N
for i in A:
if i > N:
result = 0
break
elif i <= N and not A_[i-1]:
A_[i-1] = 1
count -= 1
if count:
result = 0
return result
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N) or O(N * log(N))
expand all
Correctness tests
1.
0.065 s
OK
2.
0.062 s
OK
1.
0.066 s
OK
2.
0.065 s
OK
1.
0.063 s
OK
2.
0.066 s
OK
3.
0.063 s
OK
4.
0.066 s
OK
1.
0.066 s
OK
2.
0.063 s
OK
3.
0.066 s
OK
4.
0.063 s
OK
1.
0.063 s
OK
2.
0.063 s
OK
expand all
Performance tests
1.
0.073 s
OK
2.
0.077 s
OK
1.
0.160 s
OK
2.
0.166 s
OK
1.
0.166 s
OK
2.
0.168 s
OK
1.
0.172 s
OK
2.
0.166 s
OK
1.
0.062 s
OK
2.
0.147 s
OK
3.
0.063 s
OK