Your browser is not supported. Please, update your browser or switch to a different one. Learn more about which browsers are supported.
Task description
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].
Task timeline
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
lst=set()
if M<max(A):
return []
else:
lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=len(A1)/2:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
lst=set()
if M<max(A):
return []
else:
lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
lst=set()
if M<max(A):
return []
else:
lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
if
lst=set()
if M<max(A):
return []
else:
lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
if len(A)
lst=set()
if M<max(A):
return []
else:
lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
if len(A)==1:
lst=set()
if M<max(A):
return []
else:
lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
if len(A)==1:
lst=set()
if M<max(A):
return []
else:
#lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
if len(A)==1:
lst=set()
if M<max(A):
return []
else:
#lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
Traceback (most recent call last): File "exec.py", line 149, in <module> main() File "exec.py", line 90, in main sol = __import__('solution') File "/tmp/solution.py", line 8 lst=set() ^ IndentationError: expected an indented block
Traceback (most recent call last): File "exec.py", line 149, in <module> main() File "exec.py", line 90, in main sol = __import__('solution') File "/tmp/solution.py", line 8 lst=set() ^ IndentationError: expected an indented block
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
lst=set()
if M<max(A):
return []
else:
#lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
lst=set()
if M<max(A):
return []
else:
#lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
# write your code in Python 3.6
lst=set()
if M<max(A):
return []
else:
#lst.add(codi(A.copy()))
for i in range(0,len(A)-K+1):
#print(i)
a=A.copy()
g=0
for j in range(K):
a[i+j]+=1
#print(a)
lst.add(codi(a.copy()))
lst=list(lst)
while 'p' in lst:
lst.remove('p')
lst.sort()
return lst
#pass
def codi(A1):
#print(A1)
d=set(A1)
lead=A1[0]
for i in d:
v=A1.count(i)
if v>A1.count(lead):
lead=i
if A1.count(lead)>=(len(A1)//2)+1:
#print(lead)
return lead
else:
#print(lead)
return 'p'
The following issues have been detected: timeout errors.
medium tests (N = 10000, M = 100)
Killed. Hard limit reached: 6.000 sec.
medium tests(N >= 20000, M=30000)
Killed. Hard limit reached: 6.000 sec.