Tasks Details
hard
Given an array, find all its elements that can become a leader, after increasing by 1 all of the numbers in some segment of a given length.
Task Score
100%
Correctness
100%
Performance
100%
Integers K, M and a non-empty array A consisting of N integers, not bigger than M, are given.
The leader of the array is a value that occurs in more than half of the elements of the array, and the segment of the array is a sequence of consecutive elements of the array.
You can modify A by choosing exactly one segment of length K and increasing by 1 every element within that segment.
The goal is to find all of the numbers that may become a leader after performing exactly one array modification as described above.
Write a function:
def solution(K, M, A)
that, given integers K and M and an array A consisting of N integers, returns an array of all numbers that can become a leader, after increasing by 1 every element of exactly one segment of A of length K. The returned array should be sorted in ascending order, and if there is no number that can become a leader, you should return an empty array. Moreover, if there are multiple ways of choosing a segment to turn some number into a leader, then this particular number should appear in an output array only once.
For example, given integers K = 3, M = 5 and the following array A:
A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 3the function should return [2, 3]. If we choose segment A[1], A[2], A[3] then we get the following array A:
A[0] = 2 A[1] = 2 A[2] = 4 A[3] = 2 A[4] = 2 A[5] = 2 A[6] = 3and 2 is the leader of this array. If we choose A[3], A[4], A[5] then A will appear as follows:
A[0] = 2 A[1] = 1 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = 3 A[6] = 3and 3 will be the leader.
And, for example, given integers K = 4, M = 2 and the following array:
A[0] = 1 A[1] = 2 A[2] = 2 A[3] = 1 A[4] = 2the function should return [2, 3], because choosing a segment A[0], A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the leaders, respectively.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..N];
- each element of array A is an integer within the range [1..M].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 4 minutes
Notes
not defined yet
Code: 23:57:07 UTC,
java,
autosave
Code: 23:57:22 UTC,
py,
autosave
Code: 23:57:33 UTC,
py,
autosave
Code: 23:57:43 UTC,
py,
autosave
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
Code: 23:57:52 UTC,
py,
verify,
result: Failed
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
return sorted(list(leader))
Analysis
expand all
Example tests
1.
0.036 s
WRONG ANSWER,
got [] expected [2, 3]
1.
0.036 s
WRONG ANSWER,
got [2] expected [2, 3]
Code: 23:58:24 UTC,
py,
autosave
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
return sorted(list(leader))
Code: 23:58:39 UTC,
py,
autosave
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
for i in range(length - K):
countr[incarr[i]] -= 1
countr[incarr[i + K]] -= 1
incarr[i] -= 1
incarr[i + K] += 1
countr[incarr[i]] += 1
countr[incarr[i + K]] += 1
if countr[incarr[i]] >= half: leader.add(incarr[i])
if countr[incarr[i + K]] >= half: leader.add(incarr[i + K])
return sorted(list(leader))
Code: 23:58:50 UTC,
py,
autosave
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
for i in range(length - K):
countr[incarr[i]] -= 1
countr[incarr[i + K]] -= 1
incarr[i] -= 1
incarr[i + K] += 1
countr[incarr[i]] += 1
countr[incarr[i + K]] += 1
if countr[incarr[i]] >= half: leader.add(incarr[i])
if countr[incarr[i + K]] >= half: leader.add(incarr[i + K])
return sorted(list(leader))
Code: 23:59:00 UTC,
py,
autosave
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
for i in range(length - K):
countr[incarr[i]] -= 1
countr[incarr[i + K]] -= 1
incarr[i] -= 1
incarr[i + K] += 1
countr[incarr[i]] += 1
countr[incarr[i + K]] += 1
if countr[incarr[i]] >= half: leader.add(incarr[i])
if countr[incarr[i + K]] >= half: leader.add(incarr[i + K])
return sorted(list(leader))
Code: 23:59:11 UTC,
py,
verify,
result: Failed
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
#(k,v) = countr.most_common(1)[0]
#if v >= half: leader.add(k)
for i in range(length - K):
countr[incarr[i]] -= 1
countr[incarr[i + K]] -= 1
incarr[i] -= 1
incarr[i + K] += 1
countr[incarr[i]] += 1
countr[incarr[i + K]] += 1
if countr[incarr[i]] >= half: leader.add(incarr[i])
if countr[incarr[i + K]] >= half: leader.add(incarr[i + K])
return sorted(list(leader))
Analysis
Code: 23:59:28 UTC,
py,
verify,
result: Passed
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
for i in range(length - K):
countr[incarr[i]] -= 1
countr[incarr[i + K]] -= 1
incarr[i] -= 1
incarr[i + K] += 1
countr[incarr[i]] += 1
countr[incarr[i + K]] += 1
if countr[incarr[i]] >= half: leader.add(incarr[i])
if countr[incarr[i + K]] >= half: leader.add(incarr[i + K])
return sorted(list(leader))
Analysis
Code: 00:00:18 UTC,
py,
verify,
result: Passed
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
for i in range(length - K):
countr[incarr[i]] -= 1
countr[incarr[i + K]] -= 1
incarr[i] -= 1
incarr[i + K] += 1
countr[incarr[i]] += 1
countr[incarr[i + K]] += 1
if countr[incarr[i]] >= half: leader.add(incarr[i])
if countr[incarr[i + K]] >= half: leader.add(incarr[i + K])
return sorted(list(leader))
Analysis
Code: 00:00:20 UTC,
py,
final,
score:
100
def solution(K, M, A):
from collections import Counter
from operator import add
length = len(A)
leader = set()
half = (length + 1) / 2
ones = [1 for _ in range(K)]
incarr = list(map(add,A,ones)) + A[K:]
countr = Counter(incarr)
(k,v) = countr.most_common(1)[0]
if v >= half: leader.add(k)
for i in range(length - K):
countr[incarr[i]] -= 1
countr[incarr[i + K]] -= 1
incarr[i] -= 1
incarr[i + K] += 1
countr[incarr[i]] += 1
countr[incarr[i + K]] += 1
if countr[incarr[i]] >= half: leader.add(incarr[i])
if countr[incarr[i + K]] >= half: leader.add(incarr[i + K])
return sorted(list(leader))
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M)
expand all
Correctness tests
1.
0.040 s
OK
2.
0.040 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
5.
0.036 s
OK
6.
0.040 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
1.
0.040 s
OK
2.
0.040 s
OK
1.
0.036 s
OK
2.
0.040 s
OK
1.
0.040 s
OK
2.
0.040 s
OK
3.
0.040 s
OK
expand all
Performance tests
1.
0.064 s
OK
2.
0.072 s
OK
3.
0.076 s
OK
1.
0.112 s
OK
2.
0.084 s
OK
3.
0.092 s
OK
1.
0.456 s
OK
2.
0.452 s
OK
3.
0.420 s
OK
1.
0.156 s
OK
2.
0.260 s
OK