Tasks Details
easy
1.
EquiLeader
Find the index S such that the leaders of the sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same.
Task Score
100%
Correctness
100%
Performance
100%
A non-empty array A consisting of N integers is given.
The leader of this array is the value that occurs in more than half of the elements of A.
An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.
For example, given array A such that:
A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2we can find two equi leaders:
- 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
- 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.
The goal is to count the number of equi leaders.
Write a function:
def solution(A)
that, given a non-empty array A consisting of N integers, returns the number of equi leaders.
For example, given:
A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2the function should return 2, as explained above.
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,000..1,000,000,000].
Copyright 2009–2025 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
Code: 20:23:58 UTC,
java,
autosave
Code: 20:24:08 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
def solution(A):
idx = -1
size = 0
for i in range(len(A)):
if size == 0:
idx = i
size = 1
elif A[i] != A[idx]:
size = size - 1
elif A[i] == A[idx]:
size = size +1
cnt = 0
for a in A:
if a == A[idx]: cnt = cnt +1
if cnt <= len(A)/2:
return -1
cnt_left = 0
cnt_equiLeader = 0
for i in range(len(A)):
if A[i] == A[idx]:
cnt_left = cnt_left +1
if cnt_left > (i+1)/2 and (cnt - cnt_left) > (len(A) - i -1)/2:
cnt_equiLeader = cnt_equiLeader + 1
return cnt_equiLeader
Code: 20:24: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):
def solution(A):
idx = -1
size = 0
for i in range(len(A)):
if size == 0:
idx = i
size = 1
elif A[i] != A[idx]:
size = size - 1
elif A[i] == A[idx]:
size = size +1
cnt = 0
for a in A:
if a == A[idx]: cnt = cnt +1
if cnt <= len(A)/2:
return 0
cnt_left = 0
cnt_equiLeader = 0
for i in range(len(A)):
if A[i] == A[idx]:
cnt_left = cnt_left +1
if cnt_left > (i+1)/2 and (cnt - cnt_left) > (len(A) - i -1)/2:
cnt_equiLeader = cnt_equiLeader + 1
return cnt_equiLeader
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 6
idx = -1
^
IndentationError: expected an indented block
Code: 20:24:23 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
def solution(A):
idx = -1
size = 0
for i in range(len(A)):
if size == 0:
idx = i
size = 1
elif A[i] != A[idx]:
size = size - 1
elif A[i] == A[idx]:
size = size +1
cnt = 0
for a in A:
if a == A[idx]: cnt = cnt +1
if cnt <= len(A)/2:
return 0
cnt_left = 0
cnt_equiLeader = 0
for i in range(len(A)):
if A[i] == A[idx]:
cnt_left = cnt_left +1
if cnt_left > (i+1)/2 and (cnt - cnt_left) > (len(A) - i -1)/2:
cnt_equiLeader = cnt_equiLeader + 1
return cnt_equiLeader
User test case 1:
[1, 2]
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 6
idx = -1
^
IndentationError: expected an indented block
expand all
User 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 6
idx = -1
^
IndentationError: expected an indented block
Code: 20:24:32 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
idx = -1
size = 0
for i in range(len(A)):
if size == 0:
idx = i
size = 1
elif A[i] != A[idx]:
size = size - 1
elif A[i] == A[idx]:
size = size +1
cnt = 0
for a in A:
if a == A[idx]: cnt = cnt +1
if cnt <= len(A)/2:
return 0
cnt_left = 0
cnt_equiLeader = 0
for i in range(len(A)):
if A[i] == A[idx]:
cnt_left = cnt_left +1
if cnt_left > (i+1)/2 and (cnt - cnt_left) > (len(A) - i -1)/2:
cnt_equiLeader = cnt_equiLeader + 1
return cnt_equiLeader
User test case 1:
[1, 2]
Analysis
Code: 20:24:39 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
idx = -1
size = 0
for i in range(len(A)):
if size == 0:
idx = i
size = 1
elif A[i] != A[idx]:
size = size - 1
elif A[i] == A[idx]:
size = size +1
cnt = 0
for a in A:
if a == A[idx]: cnt = cnt +1
if cnt <= len(A)/2:
return 0
cnt_left = 0
cnt_equiLeader = 0
for i in range(len(A)):
if A[i] == A[idx]:
cnt_left = cnt_left +1
if cnt_left > (i+1)/2 and (cnt - cnt_left) > (len(A) - i -1)/2:
cnt_equiLeader = cnt_equiLeader + 1
return cnt_equiLeader
User test case 1:
[1, 2]
Analysis
Code: 20:24:41 UTC,
py,
final,
score:
100
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
idx = -1
size = 0
for i in range(len(A)):
if size == 0:
idx = i
size = 1
elif A[i] != A[idx]:
size = size - 1
elif A[i] == A[idx]:
size = size +1
cnt = 0
for a in A:
if a == A[idx]: cnt = cnt +1
if cnt <= len(A)/2:
return 0
cnt_left = 0
cnt_equiLeader = 0
for i in range(len(A)):
if A[i] == A[idx]:
cnt_left = cnt_left +1
if cnt_left > (i+1)/2 and (cnt - cnt_left) > (len(A) - i -1)/2:
cnt_equiLeader = cnt_equiLeader + 1
return cnt_equiLeaderAnalysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
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
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK