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 1 minutes
Notes
not defined yet
Code: 05:53:41 UTC,
java,
autosave
Code: 05:53:59 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# Reduce the count D[str_x] by 1
def dict_minus(D, str_x):
# assume str_x in D
count = D[str_x] - 1
if count >= 1:
D[str_x] = count
else: # count == 0
D.pop(str_x)
return D
# Increase the count D[str_x] by 1
def dict_plus(D, str_x):
if str_x in D:
count = D[str_x]
else:
count = 0
D[str_x] = count + 1
return D
#
def find_leader2(K, M, A):
# find the unique_list count
A_list = list(A)
unique_list = dict()
for x in A_list:
str_x = str(x)
if str_x not in unique_list:
unique_list[str_x] = 1
else:
unique_list[str_x] = unique_list[str_x]+1
N = len(A)
leader = []
for i in range(N-K+1):
if i == 0:
A_plus_count = unique_list.copy()
for j in range(i, i+K):
str_Aj = str(A[j])
A_plus_count = dict_minus(A_plus_count, str_Aj)
#
str_Ajp1 = str(A[j]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
else: # only two entries changed counts from i-1
str_Ajp1 = str(A[i-1]+1)
A_plus_count = dict_minus(A_plus_count, str_Ajp1)
str_Aj = str(A[i-1])
A_plus_count = dict_plus(A_plus_count, str_Aj)
#
str_Aj = str(A[i+K-1])
A_plus_count = dict_minus(A_plus_count, str_Aj)
str_Ajp1 = str(A[i+K-1]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
#
if i == 0:
for str_x in A_plus_count:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
else: # i > 0, only 2 entries increased counts
for str_x in [str(A[i-1]), str(A[i+K-1]+1)]:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
# end for i in rang(N-K+1)
leader.sort()
return leader # assending by default pass
Code: 05:54:07 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# Reduce the count D[str_x] by 1
def dict_minus(D, str_x):
# assume str_x in D
count = D[str_x] - 1
if count >= 1:
D[str_x] = count
else: # count == 0
D.pop(str_x)
return D
# Increase the count D[str_x] by 1
def dict_plus(D, str_x):
if str_x in D:
count = D[str_x]
else:
count = 0
D[str_x] = count + 1
return D
#
def solution(K, M, A):
# find the unique_list count
A_list = list(A)
unique_list = dict()
for x in A_list:
str_x = str(x)
if str_x not in unique_list:
unique_list[str_x] = 1
else:
unique_list[str_x] = unique_list[str_x]+1
N = len(A)
leader = []
for i in range(N-K+1):
if i == 0:
A_plus_count = unique_list.copy()
for j in range(i, i+K):
str_Aj = str(A[j])
A_plus_count = dict_minus(A_plus_count, str_Aj)
#
str_Ajp1 = str(A[j]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
else: # only two entries changed counts from i-1
str_Ajp1 = str(A[i-1]+1)
A_plus_count = dict_minus(A_plus_count, str_Ajp1)
str_Aj = str(A[i-1])
A_plus_count = dict_plus(A_plus_count, str_Aj)
#
str_Aj = str(A[i+K-1])
A_plus_count = dict_minus(A_plus_count, str_Aj)
str_Ajp1 = str(A[i+K-1]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
#
if i == 0:
for str_x in A_plus_count:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
else: # i > 0, only 2 entries increased counts
for str_x in [str(A[i-1]), str(A[i+K-1]+1)]:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
# end for i in rang(N-K+1)
leader.sort()
return leader # assending by default pass
Code: 05:54:15 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# Reduce the count D[str_x] by 1
def dict_minus(D, str_x):
# assume str_x in D
count = D[str_x] - 1
if count >= 1:
D[str_x] = count
else: # count == 0
D.pop(str_x)
return D
# Increase the count D[str_x] by 1
def dict_plus(D, str_x):
if str_x in D:
count = D[str_x]
else:
count = 0
D[str_x] = count + 1
return D
#
def solution(K, M, A):
# find the unique_list count
A_list = list(A)
unique_list = dict()
for x in A_list:
str_x = str(x)
if str_x not in unique_list:
unique_list[str_x] = 1
else:
unique_list[str_x] = unique_list[str_x]+1
N = len(A)
leader = []
for i in range(N-K+1):
if i == 0:
A_plus_count = unique_list.copy()
for j in range(i, i+K):
str_Aj = str(A[j])
A_plus_count = dict_minus(A_plus_count, str_Aj)
#
str_Ajp1 = str(A[j]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
else: # only two entries changed counts from i-1
str_Ajp1 = str(A[i-1]+1)
A_plus_count = dict_minus(A_plus_count, str_Ajp1)
str_Aj = str(A[i-1])
A_plus_count = dict_plus(A_plus_count, str_Aj)
#
str_Aj = str(A[i+K-1])
A_plus_count = dict_minus(A_plus_count, str_Aj)
str_Ajp1 = str(A[i+K-1]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
#
if i == 0:
for str_x in A_plus_count:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
else: # i > 0, only 2 entries increased counts
for str_x in [str(A[i-1]), str(A[i+K-1]+1)]:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
# end for i in rang(N-K+1)
leader.sort()
return leader # assending by default
pass
Analysis
Code: 05:54:20 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# Reduce the count D[str_x] by 1
def dict_minus(D, str_x):
# assume str_x in D
count = D[str_x] - 1
if count >= 1:
D[str_x] = count
else: # count == 0
D.pop(str_x)
return D
# Increase the count D[str_x] by 1
def dict_plus(D, str_x):
if str_x in D:
count = D[str_x]
else:
count = 0
D[str_x] = count + 1
return D
#
def solution(K, M, A):
# find the unique_list count
A_list = list(A)
unique_list = dict()
for x in A_list:
str_x = str(x)
if str_x not in unique_list:
unique_list[str_x] = 1
else:
unique_list[str_x] = unique_list[str_x]+1
N = len(A)
leader = []
for i in range(N-K+1):
if i == 0:
A_plus_count = unique_list.copy()
for j in range(i, i+K):
str_Aj = str(A[j])
A_plus_count = dict_minus(A_plus_count, str_Aj)
#
str_Ajp1 = str(A[j]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
else: # only two entries changed counts from i-1
str_Ajp1 = str(A[i-1]+1)
A_plus_count = dict_minus(A_plus_count, str_Ajp1)
str_Aj = str(A[i-1])
A_plus_count = dict_plus(A_plus_count, str_Aj)
#
str_Aj = str(A[i+K-1])
A_plus_count = dict_minus(A_plus_count, str_Aj)
str_Ajp1 = str(A[i+K-1]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
#
if i == 0:
for str_x in A_plus_count:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
else: # i > 0, only 2 entries increased counts
for str_x in [str(A[i-1]), str(A[i+K-1]+1)]:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
# end for i in rang(N-K+1)
leader.sort()
return leader # assending by default
pass
Analysis
Code: 05:54:21 UTC,
py,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# Reduce the count D[str_x] by 1
def dict_minus(D, str_x):
# assume str_x in D
count = D[str_x] - 1
if count >= 1:
D[str_x] = count
else: # count == 0
D.pop(str_x)
return D
# Increase the count D[str_x] by 1
def dict_plus(D, str_x):
if str_x in D:
count = D[str_x]
else:
count = 0
D[str_x] = count + 1
return D
#
def solution(K, M, A):
# find the unique_list count
A_list = list(A)
unique_list = dict()
for x in A_list:
str_x = str(x)
if str_x not in unique_list:
unique_list[str_x] = 1
else:
unique_list[str_x] = unique_list[str_x]+1
N = len(A)
leader = []
for i in range(N-K+1):
if i == 0:
A_plus_count = unique_list.copy()
for j in range(i, i+K):
str_Aj = str(A[j])
A_plus_count = dict_minus(A_plus_count, str_Aj)
#
str_Ajp1 = str(A[j]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
else: # only two entries changed counts from i-1
str_Ajp1 = str(A[i-1]+1)
A_plus_count = dict_minus(A_plus_count, str_Ajp1)
str_Aj = str(A[i-1])
A_plus_count = dict_plus(A_plus_count, str_Aj)
#
str_Aj = str(A[i+K-1])
A_plus_count = dict_minus(A_plus_count, str_Aj)
str_Ajp1 = str(A[i+K-1]+1)
A_plus_count = dict_plus(A_plus_count, str_Ajp1)
#
if i == 0:
for str_x in A_plus_count:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
else: # i > 0, only 2 entries increased counts
for str_x in [str(A[i-1]), str(A[i+K-1]+1)]:
x = int(str_x)
if (A_plus_count[str_x] > N/2) and (x not in leader):
leader.append(x)
# end for i in rang(N-K+1)
leader.sort()
return leader # assending by default
pass
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
expand all
Performance tests
1.
0.100 s
OK
2.
0.112 s
OK
3.
0.108 s
OK
1.
0.192 s
OK
2.
0.136 s
OK
3.
0.140 s
OK
1.
0.844 s
OK
2.
0.832 s
OK
3.
0.816 s
OK
1.
0.344 s
OK
2.
0.528 s
OK