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
55%
Correctness
100%
Performance
0%
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:
class Solution { public int[] solution(int K, int M, int[] 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 Java 21
Time spent on task 2 minutes
Notes
not defined yet
Code: 09:04:41 UTC,
java,
autosave
Code: 09:05:00 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int K, int M, int[] A) {List<Integer> leads = new ArrayList<>();
for (int i = 0; i+K <= A.length; i++) {
int seg = 0;
int[] changed = Arrays.copyOf(A,A.length);
while(seg<K){
changed[i+seg]= A[i+seg]+1;
seg++;
}
int lead = getLead(M, changed);
if (lead > 0 && !leads.contains(lead)) {
leads.add(lead);
}
}
int leadArr[] = new int[leads.size()];
for (int l = 0; l < leads.size(); l++) {
leadArr[l] = leads.get(l);
}
Arrays.sort(leadArr);
return leadArr;
}
private int getLead(int m, int[] changed) {
int leader = 0;
int[] count = new int[m+1];
for (int i : changed) {
count[i - 1] = count[i - 1] + 1;
}
int num = 1, maxCount = 0, maxNum = 1;
for (int i : count) {
if (i > maxCount) {
maxCount = i;
maxNum = num;
}
num++;
}
if (maxCount > changed.length / 2) {
leader = maxNum;
}
System.out.println(ArrayUtils.toString(changed)+"----"+leader);
return leader;// write your code in Java SE 8
}
}
Analysis
Compile error
Solution.java:8: error: cannot find symbol
public int[] solution(int K, int M, int[] A) {List<Integer> leads = new ArrayList<>();
^
symbol: class List
location: class Solution
Solution.java:8: error: cannot find symbol
public int[] solution(int K, int M, int[] A) {List<Integer> leads = new ArrayList<>();
^
symbol: class ArrayList
location: class Solution
Solution.java:11: error: cannot find symbol
int[] changed = Arrays.copyOf(A,A.length);
^
symbol: variable Arrays
location: class Solution
Solution.java:26: error: cannot find symbol
Arrays.sort(leadArr);
^
symbol: variable Arrays
location: class Solution
Solution.java:50: error: cannot find symbol
System.out.println(ArrayUtils.toString(changed)+"----"+leader);
^
symbol: variable ArrayUtils
location: class Solution
5 errors
Code: 09:05:08 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public int[] solution(int K, int M, int[] A) {List<Integer> leads = new ArrayList<>();
for (int i = 0; i+K <= A.length; i++) {
int seg = 0;
int[] changed = Arrays.copyOf(A,A.length);
while(seg<K){
changed[i+seg]= A[i+seg]+1;
seg++;
}
int lead = getLead(M, changed);
if (lead > 0 && !leads.contains(lead)) {
leads.add(lead);
}
}
int leadArr[] = new int[leads.size()];
for (int l = 0; l < leads.size(); l++) {
leadArr[l] = leads.get(l);
}
Arrays.sort(leadArr);
return leadArr;
}
private int getLead(int m, int[] changed) {
int leader = 0;
int[] count = new int[m+1];
for (int i : changed) {
count[i - 1] = count[i - 1] + 1;
}
int num = 1, maxCount = 0, maxNum = 1;
for (int i : count) {
if (i > maxCount) {
maxCount = i;
maxNum = num;
}
num++;
}
if (maxCount > changed.length / 2) {
leader = maxNum;
}
System.out.println(ArrayUtils.toString(changed)+"----"+leader);
return leader;// write your code in Java SE 8
}
}
Analysis
Compile error
Solution.java:53: error: cannot find symbol
System.out.println(ArrayUtils.toString(changed)+"----"+leader);
^
symbol: variable ArrayUtils
location: class Solution
1 error
Code: 09:05:32 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public int[] solution(int K, int M, int[] A) {List<Integer> leads = new ArrayList<>();
for (int i = 0; i+K <= A.length; i++) {
int seg = 0;
int[] changed = Arrays.copyOf(A,A.length);
while(seg<K){
changed[i+seg]= A[i+seg]+1;
seg++;
}
int lead = getLead(M, changed);
if (lead > 0 && !leads.contains(lead)) {
leads.add(lead);
}
}
int leadArr[] = new int[leads.size()];
for (int l = 0; l < leads.size(); l++) {
leadArr[l] = leads.get(l);
}
Arrays.sort(leadArr);
return leadArr;
}
private int getLead(int m, int[] changed) {
int leader = 0;
int[] count = new int[m+1];
for (int i : changed) {
count[i - 1] = count[i - 1] + 1;
}
int num = 1, maxCount = 0, maxNum = 1;
for (int i : count) {
if (i > maxCount) {
maxCount = i;
maxNum = num;
}
num++;
}
if (maxCount > changed.length / 2) {
leader = maxNum;
}
// System.out.println(ArrayUtils.toString(changed)+"----"+leader);
return leader;// write your code in Java SE 8
}
}
Analysis
Code: 09:05:47 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public int[] solution(int K, int M, int[] A) {List<Integer> leads = new ArrayList<>();
for (int i = 0; i+K <= A.length; i++) {
int seg = 0;
int[] changed = Arrays.copyOf(A,A.length);
while(seg<K){
changed[i+seg]= A[i+seg]+1;
seg++;
}
int lead = getLead(M, changed);
if (lead > 0 && !leads.contains(lead)) {
leads.add(lead);
}
}
int leadArr[] = new int[leads.size()];
for (int l = 0; l < leads.size(); l++) {
leadArr[l] = leads.get(l);
}
Arrays.sort(leadArr);
return leadArr;
}
private int getLead(int m, int[] changed) {
int leader = 0;
int[] count = new int[m+1];
for (int i : changed) {
count[i - 1] = count[i - 1] + 1;
}
int num = 1, maxCount = 0, maxNum = 1;
for (int i : count) {
if (i > maxCount) {
maxCount = i;
maxNum = num;
}
num++;
}
if (maxCount > changed.length / 2) {
leader = maxNum;
}
// System.out.println(ArrayUtils.toString(changed)+"----"+leader);
return leader;// write your code in Java SE 8
}
}
Analysis
Code: 09:05:51 UTC,
java,
final,
score:
55
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public int[] solution(int K, int M, int[] A) {List<Integer> leads = new ArrayList<>();
for (int i = 0; i+K <= A.length; i++) {
int seg = 0;
int[] changed = Arrays.copyOf(A,A.length);
while(seg<K){
changed[i+seg]= A[i+seg]+1;
seg++;
}
int lead = getLead(M, changed);
if (lead > 0 && !leads.contains(lead)) {
leads.add(lead);
}
}
int leadArr[] = new int[leads.size()];
for (int l = 0; l < leads.size(); l++) {
leadArr[l] = leads.get(l);
}
Arrays.sort(leadArr);
return leadArr;
}
private int getLead(int m, int[] changed) {
int leader = 0;
int[] count = new int[m+1];
for (int i : changed) {
count[i - 1] = count[i - 1] + 1;
}
int num = 1, maxCount = 0, maxNum = 1;
for (int i : count) {
if (i > maxCount) {
maxCount = i;
maxNum = num;
}
num++;
}
if (maxCount > changed.length / 2) {
leader = maxNum;
}
// System.out.println(ArrayUtils.toString(changed)+"----"+leader);
return leader;// write your code in Java SE 8
}
}
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N*(N+M)) or O(N**2)
expand all
Correctness tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
5.
0.012 s
OK
6.
0.012 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
expand all
Performance tests
medium_tests1
medium tests (N = 10000, M = 100)
medium tests (N = 10000, M = 100)
✘
TIMEOUT ERROR
running time: 2.216 sec., time limit: 0.100 sec.
running time: 2.216 sec., time limit: 0.100 sec.
1.
2.216 s
TIMEOUT ERROR,
running time: 2.216 sec., time limit: 0.100 sec.
2.
2.496 s
TIMEOUT ERROR,
running time: 2.496 sec., time limit: 0.100 sec.
3.
2.484 s
TIMEOUT ERROR,
running time: 2.484 sec., time limit: 0.100 sec.
medium_tests2
medium tests(N >= 20000, M=30000)
medium tests(N >= 20000, M=30000)
✘
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.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
3.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
1.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
2.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
3.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
1.
0.260 s
OK
2.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.