Computer Engineering
Codility - Equi Leader
by En.Lee
2014. 10. 26.
https://codility.com/demo/results/demoV3FC6D-GGH/
Task description A non-empty zero-indexed 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] = 2 we 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 zero-indexed 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] = 2 the function should return 2, as explained above. Assume that: - 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].
Complexity: - expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
import java.util.*;
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;
}
}
}
Detected time complexity: O(N) test | time | result |
---|
Example tests |
---|
example example test | 1.516 s | OK | Correctness tests |
---|
single single element | 1.592 s | OK | double two elements | 1.544 s | OK | simple simple test | 1.540 s | OK | small_random small random test with two values, length = ~100 | 1.524 s | OK | small random + 200 * [MIN_INT] + random ,length = ~300 | 1.516 s | OK | Performance tests |
---|
large_random large random test with two values, length = ~50,000 | 1.596 s | OK | large random(0,1) + 50000 * [0] + random(0, 1), length = ~100,000 | 1.652 s | OK | large_range 1, 2, ..., N, length = ~100,000 | 1.508 s | OK | extreme_large all the same values | 1.872 s | OK |
|