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
100%
Correctness
100%
Performance
100%
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 21
Time spent on task 52 minutes
Notes
not defined yet
Code: 17:05:29 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int size = 0;
int value = 0;
for (int i=0; i<A.length; i++) {
if (size == 0) {
size++;
value = A[i];
} else {
if (A[i] == value)
size++;
else
size--;
}
}
int count = 0;
for (int j=0; j<A.length; j++) {
if (A[j] == value) {
count++;
}
}
if (count <= (A.length/2)) {
return 0;
} else {
int indices = 0;
size = 0;
for (int k=0; k<A.length-1; k++) {
if (A[k] == value){
count--;
size++;
}
if (size > ((k+1)/2)) && (count > (A.length-(k+1))/2 ) {
indices++;
}
}
return indices;
}
}
}
Analysis
Compile error
Solution.java:43: error: illegal start of expression
if (size > ((k+1)/2)) && (count > (A.length-(k+1))/2 ) {
^
Solution.java:43: error: ';' expected
if (size > ((k+1)/2)) && (count > (A.length-(k+1))/2 ) {
^
2 errors
Code: 17:05:54 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int size = 0;
int value = 0;
for (int i=0; i<A.length; i++) {
if (size == 0) {
size++;
value = A[i];
} else {
if (A[i] == value)
size++;
else
size--;
}
}
int count = 0;
for (int j=0; j<A.length; j++) {
if (A[j] == value) {
count++;
}
}
if (count <= (A.length/2)) {
return 0;
} else {
int indices = 0;
size = 0;
for (int k=0; k<A.length-1; k++) {
if (A[k] == value){
count--;
size++;
}
if ((size > ((k+1)/2)) && (count > (A.length-(k+1))/2 )) {
indices++;
}
}
return indices;
}
}
}
Analysis
Code: 17:06:06 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int size = 0;
int value = 0;
for (int i=0; i<A.length; i++) {
if (size == 0) {
size++;
value = A[i];
} else {
if (A[i] == value)
size++;
else
size--;
}
}
int count = 0;
for (int j=0; j<A.length; j++) {
if (A[j] == value) {
count++;
}
}
if (count <= (A.length/2)) {
return 0;
} else {
int indices = 0;
size = 0;
for (int k=0; k<A.length-1; k++) {
if (A[k] == value){
count--;
size++;
}
if ((size > ((k+1)/2)) && (count > (A.length-(k+1))/2 )) {
indices++;
}
}
return indices;
}
}
}
Analysis
User test case 1:
None
Code: 17:06:34 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int size = 0;
int value = 0;
for (int i=0; i<A.length; i++) {
if (size == 0) {
size++;
value = A[i];
} else {
if (A[i] == value)
size++;
else
size--;
}
}
int count = 0;
for (int j=0; j<A.length; j++) {
if (A[j] == value) {
count++;
}
}
if (count <= (A.length/2)) {
return 0;
} else {
int indices = 0;
size = 0;
for (int k=0; k<A.length-1; k++) {
if (A[k] == value){
count--;
size++;
}
if ((size > ((k+1)/2)) && (count > (A.length-(k+1))/2 )) {
indices++;
}
}
return indices;
}
}
}
Analysis
User test case 1:
None
Code: 17:06:50 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int size = 0;
int value = 0;
for (int i=0; i<A.length; i++) {
if (size == 0) {
size++;
value = A[i];
} else {
if (A[i] == value)
size++;
else
size--;
}
}
int count = 0;
for (int j=0; j<A.length; j++) {
if (A[j] == value) {
count++;
}
}
if (count <= (A.length/2)) {
return 0;
} else {
int indices = 0;
size = 0;
for (int k=0; k<A.length-1; k++) {
if (A[k] == value){
count--;
size++;
}
if ((size > ((k+1)/2)) && (count > (A.length-(k+1))/2 )) {
indices++;
}
}
return indices;
}
}
}
Analysis
User test case 1:
None
Code: 17:07:04 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int size = 0;
int value = 0;
for (int i=0; i<A.length; i++) {
if (size == 0) {
size++;
value = A[i];
} else {
if (A[i] == value)
size++;
else
size--;
}
}
int count = 0;
for (int j=0; j<A.length; j++) {
if (A[j] == value) {
count++;
}
}
if (count <= (A.length/2)) {
return 0;
} else {
int indices = 0;
size = 0;
for (int k=0; k<A.length-1; k++) {
if (A[k] == value){
count--;
size++;
}
if ((size > ((k+1)/2)) && (count > (A.length-(k+1))/2 )) {
indices++;
}
}
return indices;
}
}
}
Analysis
User test case 1:
None
Code: 17:07:18 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int size = 0;
int value = 0;
for (int i=0; i<A.length; i++) {
if (size == 0) {
size++;
value = A[i];
} else {
if (A[i] == value)
size++;
else
size--;
}
}
int count = 0;
for (int j=0; j<A.length; j++) {
if (A[j] == value) {
count++;
}
}
if (count <= (A.length/2)) {
return 0;
} else {
int indices = 0;
size = 0;
for (int k=0; k<A.length-1; k++) {
if (A[k] == value){
count--;
size++;
}
if ((size > ((k+1)/2)) && (count > (A.length-(k+1))/2 )) {
indices++;
}
}
return indices;
}
}
}
Analysis
User test case 1:
None
Code: 17:07:26 UTC,
java,
final,
score:
100
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int size = 0;
int value = 0;
for (int i=0; i<A.length; i++) {
if (size == 0) {
size++;
value = A[i];
} else {
if (A[i] == value)
size++;
else
size--;
}
}
int count = 0;
for (int j=0; j<A.length; j++) {
if (A[j] == value) {
count++;
}
}
if (count <= (A.length/2)) {
return 0;
} else {
int indices = 0;
size = 0;
for (int k=0; k<A.length-1; k++) {
if (A[k] == value){
count--;
size++;
}
if ((size > ((k+1)/2)) && (count > (A.length-(k+1))/2 )) {
indices++;
}
}
return indices;
}
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)