Tasks Details
easy
1.
ArrListLen
Compute length of a single-link list encoded in an array.
Task Score
100%
Correctness
100%
Performance
Not assessed
A non-empty array A consisting of N integers is given.
Array A represents a linked list. A list is constructed from this array as follows:
- the first node (the head) is located at index 0;
- the value of a node located at index K is A[K];
- if the value of a node is −1 then it is the last node of the list;
- otherwise, the successor of a node located at index K is located at index A[K] (you can assume that A[K] is a valid index, that is 0 ≤ A[K] < N).
For example, for array A such that:
A[0] = 1 A[1] = 4 A[2] = -1 A[3] = 3 A[4] = 2the following list is constructed:
- the first node (the head) is located at index 0 and has a value of 1;
- the second node is located at index 1 and has a value of 4;
- the third node is located at index 4 and has a value of 2;
- the fourth node is located at index 2 and has a value of −1.
Write a function:
def solution(A)
that, given a non-empty array A consisting of N integers, returns the length of the list constructed from A in the above manner.
For example, given array A such that:
A[0] = 1 A[1] = 4 A[2] = -1 A[3] = 3 A[4] = 2the function should return 4, as explained in the example above.
Assume that:
- N is an integer within the range [1..200,000];
- each element of array A is an integer within the range [−1..N-1];
- it will always be possible to construct the list and its length will be finite.
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 7 minutes
Notes
not defined yet
Task timeline
Code: 06:40:05 UTC,
java,
autosave
Code: 06:44:54 UTC,
py,
autosave
Code: 06:44:56 UTC,
py,
verify,
result: Passed
Analysis
Code: 06:46: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):
# write your code in Python 3.6
answer=1
i=0
while True:
if A[i] == -1:
break;
else:
i = A[i]
answer+=1
return answer
User test case 1:
[-1, 1]
Analysis
Code: 06:46:13 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 3.6
answer=1
i=0
while True:
if A[i] == -1:
break;
else:
i = A[i]
answer+=1
return answer
User test case 1:
[1, -1, 1]
Analysis
Code: 06:46:30 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 3.6
answer=1
i=0
while True:
if A[i] == -1:
break;
else:
i = A[i]
answer+=1
return answer
User test case 1:
[1, 2, 3, 4, -1]
Analysis
Code: 06:46:38 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 3.6
answer=1
i=0
while True:
if A[i] == -1:
break;
else:
i = A[i]
answer+=1
return answer
User test case 1:
[1, 2, 3, 4, -1]
Analysis
Code: 06:46:40 UTC,
py,
final,
score: 
100
Analysis summary
The solution obtained perfect score.
Analysis
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
1.
0.044 s
OK
1.
0.044 s
OK
1.
0.148 s
OK
1.
0.060 s
OK
2.
0.260 s
OK