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:
class Solution { public int solution(int[] 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 Java 8
Time spent on task 111 minutes
Notes
not defined yet
Code: 04:57:54 UTC,
java,
autosave
Code: 06:47:23 UTC,
java,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
// 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[] A) {
// write your code in Java SE 8
if (A.length == 1) {
return 0;
}
// 배열 전체 갯수 중 반+1 이상이 되어야 equi leader 존재
int conditionCnt = (A.length/2)+1;
int leaderValue = 0; // 기준이 되는 leader 값
int equiLeaderCnt = 0;
// 요소 갯수 세기
HashMap<Integer, Integer> hMap = new HashMap<Integer, Integer>();
for (int n : A) {
if (hMap.containsKey(n)) {
hMap.put(n, hMap.get(n)+1);
} else {
hMap.put(n, 1);
}
}
// 기준이 되는 leader값 추출
for (Map.Entry<Integer, Integer> entry : hMap.entrySet()) {
if (conditionCnt == 0 || entry.getValue().compareTo(conditionCnt) >= 0) {
leaderValue = entry.getKey();
}
}
int[] tmpA = new int[A.length];
for (int i=0; i<A.length; i++) {
if (A[i] == leaderValue) {
tmpA[i] = 1;
} else {
tmpA[i] = 0;
}
}
// equiLeader 갯수
for (int i=1; i<tmpA.length+1; i++) {
if (tmpA[i-1] == 1) {
int hOne = 0;
int hTwo = 0;
for (int j=0; j<i; j++) {
hOne += tmpA[j];
}
for (int k=i; k<tmpA.length; k++) {
hTwo += tmpA[k];
}
//int conOne = (int) Math.ceil((double)i/2);
//int conTwo = (int) Math.ceil((double)(tmpA.length-i)/2);
int conOne = (i/2)+1;
int conTwo = ((tmpA.length-i)/2)+1;
if (hOne >= conOne && hTwo >= conTwo) {
equiLeaderCnt++;
}
}
}
// System.out.println(leaderValue); // 4
//System.out.println(hMap); // {2=1, 3=1, 4=4}
return equiLeaderCnt;
}
}
Code: 06:47:41 UTC,
java,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
import java.util.HashMap;
import java.util.Map;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 1) {
return 0;
}
// 배열 전체 갯수 중 반+1 이상이 되어야 equi leader 존재
int conditionCnt = (A.length/2)+1;
int leaderValue = 0; // 기준이 되는 leader 값
int equiLeaderCnt = 0;
// 요소 갯수 세기
HashMap<Integer, Integer> hMap = new HashMap<Integer, Integer>();
for (int n : A) {
if (hMap.containsKey(n)) {
hMap.put(n, hMap.get(n)+1);
} else {
hMap.put(n, 1);
}
}
// 기준이 되는 leader값 추출
for (Map.Entry<Integer, Integer> entry : hMap.entrySet()) {
if (conditionCnt == 0 || entry.getValue().compareTo(conditionCnt) >= 0) {
leaderValue = entry.getKey();
}
}
int[] tmpA = new int[A.length];
for (int i=0; i<A.length; i++) {
if (A[i] == leaderValue) {
tmpA[i] = 1;
} else {
tmpA[i] = 0;
}
}
// equiLeader 갯수
for (int i=1; i<tmpA.length+1; i++) {
if (tmpA[i-1] == 1) {
int hOne = 0;
int hTwo = 0;
for (int j=0; j<i; j++) {
hOne += tmpA[j];
}
for (int k=i; k<tmpA.length; k++) {
hTwo += tmpA[k];
}
//int conOne = (int) Math.ceil((double)i/2);
//int conTwo = (int) Math.ceil((double)(tmpA.length-i)/2);
int conOne = (i/2)+1;
int conTwo = ((tmpA.length-i)/2)+1;
if (hOne >= conOne && hTwo >= conTwo) {
equiLeaderCnt++;
}
}
}
// System.out.println(leaderValue); // 4
//System.out.println(hMap); // {2=1, 3=1, 4=4}
return equiLeaderCnt;
}
}
Code: 06:48:40 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
import java.util.HashMap;
import java.util.Map;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 1) {
return 0;
}
// 배열 전체 갯수 중 반+1 이상이 되어야 equi leader 존재
int conditionCnt = (A.length/2)+1;
int leaderValue = 0; // 기준이 되는 leader 값
int equiLeaderCnt = 0;
// 요소 갯수 세기
HashMap<Integer, Integer> hMap = new HashMap<Integer, Integer>();
for (int n : A) {
if (hMap.containsKey(n)) {
hMap.put(n, hMap.get(n)+1);
} else {
hMap.put(n, 1);
}
}
// 기준이 되는 leader값 추출
for (Map.Entry<Integer, Integer> entry : hMap.entrySet()) {
if (conditionCnt == 0 || entry.getValue().compareTo(conditionCnt) >= 0) {
leaderValue = entry.getKey();
}
}
int[] tmpA = new int[A.length];
for (int i=0; i<A.length; i++) {
if (A[i] == leaderValue) {
tmpA[i] = 1;
} else {
tmpA[i] = 0;
}
}
// equiLeader 갯수
for (int i=1; i<tmpA.length+1; i++) {
if (tmpA[i-1] == 1) {
int hOne = 0;
int hTwo = 0;
for (int j=0; j<i; j++) {
hOne += tmpA[j];
}
for (int k=i; k<tmpA.length; k++) {
hTwo += tmpA[k];
}
//int conOne = (int) Math.ceil((double)i/2);
//int conTwo = (int) Math.ceil((double)(tmpA.length-i)/2);
int conOne = (i/2)+1;
int conTwo = ((tmpA.length-i)/2)+1;
if (hOne >= conOne && hTwo >= conTwo) {
equiLeaderCnt++;
}
}
}
// System.out.println(leaderValue); // 4
//System.out.println(hMap); // {2=1, 3=1, 4=4}
return equiLeaderCnt;
}
}
User test case 1:
[4, 3, 4, 4, 4, 2]
User test case 2:
[4, 3, 3, 4, 3, 3, 4, 4]
User test case 3:
[1]
User test case 4:
[1, 1]
User test case 5:
[1, 1, 1]
User test case 6:
[1, 1, 1, 1]
User test case 7:
[4, 3, 3, 4, 4, 3]
User test case 8:
[4, 3, 3, 4, 4, 3, 3]
User test case 9:
[4, 3, 3, 4, 4, 3, 3]
User test case 10:
[4, 3, 3, 4, 4, 3, 3, 3]
Analysis
expand all
User tests
1.
0.008 s
OK
function result: 2
function result: 2
1.
0.008 s
OK
function result: 0
function result: 0
1.
0.008 s
OK
function result: 0
function result: 0
1.
0.004 s
OK
function result: 1
function result: 1
1.
0.004 s
OK
function result: 2
function result: 2
1.
0.004 s
OK
function result: 3
function result: 3
1.
0.008 s
OK
function result: 0
function result: 0
1.
0.008 s
OK
function result: 0
function result: 0
1.
0.008 s
OK
function result: 0
function result: 0
1.
0.004 s
OK
function result: 2
function result: 2
Code: 06:48:48 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
import java.util.HashMap;
import java.util.Map;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 1) {
return 0;
}
// 배열 전체 갯수 중 반+1 이상이 되어야 equi leader 존재
int conditionCnt = (A.length/2)+1;
int leaderValue = 0; // 기준이 되는 leader 값
int equiLeaderCnt = 0;
// 요소 갯수 세기
HashMap<Integer, Integer> hMap = new HashMap<Integer, Integer>();
for (int n : A) {
if (hMap.containsKey(n)) {
hMap.put(n, hMap.get(n)+1);
} else {
hMap.put(n, 1);
}
}
// 기준이 되는 leader값 추출
for (Map.Entry<Integer, Integer> entry : hMap.entrySet()) {
if (conditionCnt == 0 || entry.getValue().compareTo(conditionCnt) >= 0) {
leaderValue = entry.getKey();
}
}
int[] tmpA = new int[A.length];
for (int i=0; i<A.length; i++) {
if (A[i] == leaderValue) {
tmpA[i] = 1;
} else {
tmpA[i] = 0;
}
}
// equiLeader 갯수
for (int i=1; i<tmpA.length+1; i++) {
if (tmpA[i-1] == 1) {
int hOne = 0;
int hTwo = 0;
for (int j=0; j<i; j++) {
hOne += tmpA[j];
}
for (int k=i; k<tmpA.length; k++) {
hTwo += tmpA[k];
}
//int conOne = (int) Math.ceil((double)i/2);
//int conTwo = (int) Math.ceil((double)(tmpA.length-i)/2);
int conOne = (i/2)+1;
int conTwo = ((tmpA.length-i)/2)+1;
if (hOne >= conOne && hTwo >= conTwo) {
equiLeaderCnt++;
}
}
}
// System.out.println(leaderValue); // 4
//System.out.println(hMap); // {2=1, 3=1, 4=4}
return equiLeaderCnt;
}
}
User test case 1:
[4, 3, 4, 4, 4, 2]
User test case 2:
[4, 3, 3, 4, 3, 3, 4, 4]
User test case 3:
[1]
User test case 4:
[1, 1]
User test case 5:
[1, 1, 1]
User test case 6:
[1, 1, 1, 1]
User test case 7:
[4, 3, 3, 4, 4, 3]
User test case 8:
[4, 3, 3, 4, 4, 3, 3]
User test case 9:
[4, 3, 3, 4, 4, 3, 3]
User test case 10:
[4, 3, 3, 4, 4, 3, 3, 3]
Analysis
expand all
User tests
1.
0.008 s
OK
function result: 2
function result: 2
1.
0.004 s
OK
function result: 0
function result: 0
1.
0.004 s
OK
function result: 0
function result: 0
1.
0.004 s
OK
function result: 1
function result: 1
1.
0.004 s
OK
function result: 2
function result: 2
1.
0.004 s
OK
function result: 3
function result: 3
1.
0.004 s
OK
function result: 0
function result: 0
1.
0.004 s
OK
function result: 0
function result: 0
1.
0.004 s
OK
function result: 0
function result: 0
1.
0.004 s
OK
function result: 2
function result: 2
Code: 06:48:54 UTC,
java,
final,
score:
33
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
import java.util.HashMap;
import java.util.Map;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 1) {
return 0;
}
// 배열 전체 갯수 중 반+1 이상이 되어야 equi leader 존재
int conditionCnt = (A.length/2)+1;
int leaderValue = 0; // 기준이 되는 leader 값
int equiLeaderCnt = 0;
// 요소 갯수 세기
HashMap<Integer, Integer> hMap = new HashMap<Integer, Integer>();
for (int n : A) {
if (hMap.containsKey(n)) {
hMap.put(n, hMap.get(n)+1);
} else {
hMap.put(n, 1);
}
}
// 기준이 되는 leader값 추출
for (Map.Entry<Integer, Integer> entry : hMap.entrySet()) {
if (conditionCnt == 0 || entry.getValue().compareTo(conditionCnt) >= 0) {
leaderValue = entry.getKey();
}
}
int[] tmpA = new int[A.length];
for (int i=0; i<A.length; i++) {
if (A[i] == leaderValue) {
tmpA[i] = 1;
} else {
tmpA[i] = 0;
}
}
// equiLeader 갯수
for (int i=1; i<tmpA.length+1; i++) {
if (tmpA[i-1] == 1) {
int hOne = 0;
int hTwo = 0;
for (int j=0; j<i; j++) {
hOne += tmpA[j];
}
for (int k=i; k<tmpA.length; k++) {
hTwo += tmpA[k];
}
//int conOne = (int) Math.ceil((double)i/2);
//int conTwo = (int) Math.ceil((double)(tmpA.length-i)/2);
int conOne = (i/2)+1;
int conTwo = ((tmpA.length-i)/2)+1;
if (hOne >= conOne && hTwo >= conTwo) {
equiLeaderCnt++;
}
}
}
// System.out.println(leaderValue); // 4
//System.out.println(hMap); // {2=1, 3=1, 4=4}
return equiLeaderCnt;
}
}
Analysis summary
The following issues have been detected: wrong answers, timeout errors.
For example, for the input [4, 4, 2, 5, 3, 4, 4, 4] the solution returned a wrong answer (got 2 expected 3).
Analysis
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
1.
0.004 s
WRONG ANSWER,
got 2 expected 3
2.
0.004 s
OK
1.
0.008 s
WRONG ANSWER,
got 48 expected 79
1.
0.012 s
OK
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.
1.
0.560 s
OK
2.
0.004 s
WRONG ANSWER,
got 2 expected 3
1.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.