본문 바로가기
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.








Code: 07:58:46 UTC, java, final, score: 100.00
// 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;
        // A배열에서 가장많이 나오는 값을 찾는다.
        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++;
            }
        }
        
        // 값의 개수가 배열의 개수의 반 이상이 되지 않으면 0을 출력
        if (count <= (A.length/2)) {
            return 0;    
        } else {    // 반 이상되면, equi leader로 나눌 지점을 찾는다.
            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
Detected time complexity:
O(N)
testtimeresult
Example tests
example 
example test
1.516 sOK
Correctness tests
single 
single element
1.592 sOK
double 
two elements
1.544 sOK
simple 
simple test
1.540 sOK
small_random 
small random test with two values, length = ~100
1.524 sOK
small 
random + 200 * [MIN_INT] + random ,length = ~300
1.516 sOK
Performance tests
large_random 
large random test with two values, length = ~50,000
1.596 sOK
large 
random(0,1) + 50000 * [0] + random(0, 1), length = ~100,000
1.652 sOK
large_range 
1, 2, ..., N, length = ~100,000
1.508 sOK
extreme_large 
all the same values
1.872 sOK