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
33%
Correctness
60%
Performance
0%
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 14 minutes
Notes
not defined yet
Task timeline
Code: 11:16:29 UTC,
java,
autosave
Code: 11:16:39 UTC,
py,
autosave
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]):
if A[:i + 1].count(lead_num) > (i+1) / 2 and A[i+1 : ].count(lead_num) > (a_length - i - 1) / 2:
answer += 1
return answer
Code: 11:17:03 UTC,
py,
autosave
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]):
if A[:i + 1].count(lead_num) > (i+1) / 2
A[i+1 : ].count(lead_num) > (a_length - i - 1) / 2:
answer += 1
return answer
Code: 11:17:15 UTC,
py,
autosave
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]):
if A[:i + 1].count(lead_num) > (i+1) / 2 and A[i+1 : ].count(lead_num) > (a_length - i - 1) / 2:
answer += 1
return answer
Code: 11:17:35 UTC,
py,
autosave
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]):
if A[:i + 1].count(lead_num) > (i+1) / 2
and A[i+1 : ].count(lead_num) > (a_length - i - 1) / 2:
answer += 1
return answer
Code: 11:17:45 UTC,
py,
autosave
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]):
for
#if A[:i + 1].count(lead_num) > (i+1) / 2
#and A[i+1 : ].count(lead_num) > (a_length - i - 1) / 2:
# answer += 1
return answer
Code: 11:17:59 UTC,
py,
autosave
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]):
temp_count = 0
for num in tempp
#if A[:i + 1].count(lead_num) > (i+1) / 2
#and A[i+1 : ].count(lead_num) > (a_length - i - 1) / 2:
# answer += 1
return answer
Code: 11:18:16 UTC,
py,
autosave
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]):
temp_count = 0
for num in A[:i + 1]:
#if A[:i + 1].count(lead_num) > (i+1) / 2
#and A[i+1 : ].count(lead_num) > (a_length - i - 1) / 2:
# answer += 1
return answer
Code: 11:18:47 UTC,
py,
autosave
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
for num in A[:i + 1]:
t
#if A[:i + 1].count(lead_num) > (i+1) / 2
#and A[i+1 : ].count(lead_num) > (a_length - i - 1) / 2:
# answer += 1
return answer
Code: 11:19:09 UTC,
py,
autosave
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
for num in A[:i + 1]:
t
return answer
Code: 11:19: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
for num in A[:i + 1]:
first_count >
return answer
Code: 11:20:01 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
for num in A[:i + 1]:
if num ==
first_count >
return answer
Code: 11:20:16 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
for num in A[:i + 1]:
if num == lead_num:
first_count >
return answer
Code: 11:20:25 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
for num in A[:i + 1]:
if num == lead_num:
first_count >
return answer
Code: 11:20:49 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
for num in A[:i + 1]:
if num == lead_num:
first_count > i
return answer
Code: 11:21:04 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
for num in A[:i + 1]:
if num == lead_num:
first_count > i + 1
return answer
Code: 11:21:35 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_fi
for num in A[:i + 1]:
if num == lead_num:
first_count > i + 1
return answer
Code: 11:21:46 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 > i + 1
return answer
Code: 11:21:57 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 > i + 1
if
return answer
Code: 11:22:08 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 > i + 1
if first_count > i:
return answer
Code: 11:22:25 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:
if first_count > i:
return answer
Code: 11:24:32 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:
if first_count > i + :
return answer
Code: 11:24:43 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:
if first_count > i + 1:
is_first
return answer
Code: 11:25:04 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:
if first_count > i + 1:
is_first = True
if is_first:
return answer
Code: 11:25:31 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:
if first_count > i + 1:
is_first = True
if is_first:
for num in A[]
else:
continue
return answer
Code: 11:25:53 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:
if first_count > i + 1:
is_first = True
if is_first:
for num in A[i + 1:]:
if num == lead_num:
else:
continue
return answer
Code: 11:26:07 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:
if first_count > i + 1:
is_first = True
if is_first:
second_count = 0
for num in A[i + 1:]:
if num == lead_num:
else:
continue
return answer
Code: 11:26:38 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:
is_first = True
if is_first:
second_count = 0
for num in A[i + 1:]:
if num == lead_num:
secound_count += 1
if se
else:
continue
return answer
Code: 11:26:57 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:
is_first = True
if is_first:
second_count = 0
for num in A[i + 1:]:
if num == lead_num:
secound_count += 1
if second_count > (a_length - i - 1)
else:
continue
return answer
Code: 11:27:25 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:
secound_count += 1
if second_count > (a_length - i - 1) / 2:
else:
continue
return answer
Code: 11:27:50 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:
secound_count += 1
if second_count > (a_length - i - 1) / 2:
if_second
else:
continue
return answer
Code: 11:28:03 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:
secound_count += 1
if second_count > (a_length - i - 1) / 2:
else:
continue
return answer
Code: 11:28:27 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:
secound_count += 1
if second_count > (a_length - i - 1) / 2:
answer += 1
continue
else:
continue
return answer
Code: 11:28:37 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:28:47 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:29:18 UTC,
py,
verify,
result: Passed
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
Analysis
Code: 11:29:28 UTC,
py,
verify,
result: Passed
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
Analysis
Code: 11:29:31 UTC,
py,
final,
score:
33
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
Analysis summary
The following issues have been detected: wrong answers, timeout errors.
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
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
WRONG ANSWER,
got 348 expected 79
1.
0.044 s
WRONG ANSWER,
got 2500 expected 99
expand all
Performance tests
large_random
large random test with two values, length = ~50,000
large random test with two values, length = ~50,000
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
large
random(0,1) + 50000 * [0] + random(0, 1), length = ~100,000
random(0,1) + 50000 * [0] + random(0, 1), length = ~100,000
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
large_range
1, 2, ..., N, length = ~100,000
1, 2, ..., N, length = ~100,000
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
0.036 s
OK
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.