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 30 minutes
Notes
not defined yet
Task timeline
Code: 11:44:15 UTC,
java,
autosave
Code: 11:44:30 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer=0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
for i , _ in enumerate(A[:-1]):
first_count = 0
is_first = False
for num in A[:i + 1]:
if num == lead_num:
first_count += 1
if first_count > (i + 1) / 2:
is_first = True
if is_first:
second_count = 0
for num in A[i + 1:]:
if num == lead_num:
second_count += 1
if second_count > (a_length - i - 1) / 2:
answer += 1
continue
else:
continue
return answer
Code: 11:44:40 UTC,
py,
autosave
Code: 11:44:44 UTC,
py,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.036 s
WRONG ANSWER,
got 0 expected 2
stdout:
4
Code: 11:45:43 UTC,
py,
autosave
Code: 11:46:29 UTC,
py,
autosave
Code: 11:46:54 UTC,
py,
autosave
Code: 11:48:32 UTC,
py,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Invalid result type, int expected, <class 'NoneType'> found.stdout:
4 3 4 4 4 2
Code: 11:48:48 UTC,
py,
autosave
Code: 11:50:15 UTC,
py,
autosave
Code: 11:54:32 UTC,
py,
autosave
Code: 11:54:53 UTC,
py,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Invalid result type, int expected, <class 'NoneType'> found.stdout:
4
Code: 11:55:14 UTC,
py,
autosave
Code: 11:55:29 UTC,
py,
autosave
Code: 11:55:59 UTC,
py,
autosave
Code: 11:56:10 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
for i, num in enumerate(A):
Code: 11:57:23 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
for i, num in enumerate(A):
Code: 11:58:25 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
for i, num in enumerate(A):
c
Code: 11:58:36 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
count = 0
for i, num in enumerate(A):
Code: 11:59:05 UTC,
py,
verify,
result: Failed
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
count = 0
for i, num in enumerate(A):
print(i, num)
Analysis
expand all
Example tests
1.
0.044 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Invalid result type, int expected, <class 'NoneType'> found.stdout:
4 0 4 1 3 2 4 3 4 4 4 5 2
Code: 11:59:13 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
count = 0
for i, num in enumerate(A):
Code: 11:59:31 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
count = 0
for i, num in enumerate(A):
lead_hash[i] =
Code: 12:04:04 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
count = 0
for i, num in enumerate(A):
lead_hash[i] = 나는
Code: 12:04:30 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
print(lead_num)
lead_hash = collections.defaultdict(int)
count = 0
for i, num in enumerate(A):
if num == 4:
count += 1
lead_hash[i] = count
Code: 12:04:43 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == 4:
count += 1
lead_hash[i] = count
Code: 12:04:53 UTC,
py,
autosave
Code: 12:05:10 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == 4:
count += 1
Code: 12:05:25 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
Code: 12:05:36 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
Code: 12:06:06 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
Code: 12:07:49 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if
Code: 12:08:56 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if cou
Code: 12:09:16 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2
Code: 12:09:37 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and
Code: 12:10:08 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a
Code: 12:10:19 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
break
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and
Code: 12:10:30 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and
Code: 12:11:07 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a
Code: 12:11:24 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num]
Code: 12:11:34 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] -
Code: 12:11:48 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count>
Code: 12:12:15 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count > (a_length - i - 1) /2
Code: 12:12:26 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
answer = []
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count > (a_length - i - 1) /2 :
answer += 1
Code: 12:12:36 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count > (a_length - i - 1) /2 :
answer += 1
Code: 12:12:47 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
answer = 0
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count > (a_length - i - 1) /2 :
answer += 1
Code: 12:12:58 UTC,
py,
autosave
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
answer = 0
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count > (a_length - i - 1) /2 :
answer += 1
print(answer)
Code: 12:13:07 UTC,
py,
verify,
result: Passed
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
answer = 0
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count > (a_length - i - 1) /2 :
answer += 1
return answer
Analysis
Code: 12:13:13 UTC,
py,
verify,
result: Passed
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
answer = 0
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count > (a_length - i - 1) /2 :
answer += 1
return answer
Analysis
Code: 12:13:26 UTC,
py,
final,
score: 
100
import collections
def solution(A):
a_length = len(A)
a_hash = collections.defaultdict(int)
lead_num = 0
for i, num in enumerate(A):
a_hash[num] += 1
if a_hash[num] > a_length/2:
lead_num = num
answer = 0
count = 0
for i, num in enumerate(A):
if num == lead_num:
count += 1
if count > (i + 1) / 2 and a_hash[lead_num] - count > (a_length - i - 1) /2 :
answer += 1
return answer
Analysis 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