Test results - Codility

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] = 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 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.

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].

Solution

Programming language used Java 8

Time spent on task 26 minutes

Notes

not defined yet

Code: 06:26:02 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        
        for(int i=0; i + 1 < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len - i)/2 ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
            return new Leader(A[indexOfCandidate], countRepetitions);
        }
        return null;
    }
}

Analysis

Compile error

Solution.java:12: error: ')' expected
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len - i)/2 ) {
                                                                                           ^
1 error

Code: 06:26:14 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        
        for(int i=0; i + 1 < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len - i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
            return new Leader(A[indexOfCandidate], countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.358 s

WRONG ANSWER, got 0 expected 2

Code: 06:26:36 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len - i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
            return new Leader(A[indexOfCandidate], countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.344 s

WRONG ANSWER, got 0 expected 2

Code: 06:29:11 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len-1 - i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
            return new Leader(A[indexOfCandidate], countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.326 s

WRONG ANSWER, got 0 expected 2

Code: 06:31:12 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len-1 - i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.330 s

WRONG ANSWER, got 0 expected 2

Code: 06:33:00 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len- i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

0.981 s

WRONG ANSWER, got 0 expected 2

stdout:

v: 4, o:0

Code: 06:34:52 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        //System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len- i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
             System.out.println("v: " + candidate + ", o:" + countRepetitions);
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.056 s

WRONG ANSWER, got 0 expected 2

stdout:

v: 4, o:4

Code: 06:35:22 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len- i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
             System.out.println("v: " + candidate + ", c:" + countRepetitions);
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.353 s

WRONG ANSWER, got 0 expected 2

stdout:

v: 4, c:4
v: 4, o:0

Code: 06:35:45 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len- i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {
             System.out.println("v: " + candidate + ", c:" + countRepetitions);
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.345 s

WRONG ANSWER, got 0 expected 2

stdout:

v: 4, c:4
v: 4, o:0

Code: 06:36:27 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len- i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int occurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
            System.out.println("v: " +  this.value + ", c:" + this.ocurrences);
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.367 s

WRONG ANSWER, got 0 expected 2

stdout:

v: 4, c:0
v: 4, o:0

Code: 06:36:46 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len- i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
            System.out.println("v: " +  this.value + ", c:" + this.ocurrences);
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 1 expected 2

1.370 s

WRONG ANSWER, got 1 expected 2

stdout:

v: 4, c:4
v: 4, o:4

Code: 06:37:14 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        //System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len-1- i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 3 expected 2

1.376 s

WRONG ANSWER, got 3 expected 2

Code: 06:37:32 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        //System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
            }
            
            if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len- i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 1 expected 2

1.446 s

WRONG ANSWER, got 1 expected 2

Code: 06:37:56 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        //System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
                if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len- i)/2) ) {
                    ++equileaders;
                }
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 2

1.319 s

WRONG ANSWER, got 0 expected 2

Code: 06:38:03 UTC, java, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        //System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
                if ((leaderCounter > (i/2) && (leader.ocurrences - leaderCounter)>(len-1- i)/2) ) {
                    ++equileaders;
                }
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✔

1.328 s

Code: 06:38:40 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        //System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;
                if ((leaderCounter > (i+1/2) && (leader.ocurrences - leaderCounter)>(len-1- i)/2) ) {
                    ++equileaders;
                }
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 1 expected 2

1.329 s

WRONG ANSWER, got 1 expected 2

Code: 06:39:46 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        //System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;                
            }
            if ((leaderCounter > (i+1/2) && (leader.ocurrences - leaderCounter)>(len-1-i)/2) ) {
                    ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 1 expected 2

1.319 s

WRONG ANSWER, got 1 expected 2

Code: 06:41:20 UTC, java, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        //System.out.println("v: " + leader.value + ", o:" + leader.ocurrences);
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;                
            }
            if ((leaderCounter > (i+1)/2 && (leader.ocurrences - leaderCounter)>(len-1-i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✔

1.340 s

Code: 06:42:06 UTC, java, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;                
            }
            if ((leaderCounter > (i+1)/2 && (leader.ocurrences - leaderCounter)>(len-1-i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis

expand all Example tests

▶

example
example test

✔

1.337 s

Code: 06:42:11 UTC, java, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

class Solution {
    public int solution(int[] A) {
        Leader leader = getLeader(A);
        if ( leader == null ) { return 0; }
        int equileaders = 0, leaderCounter =0, len = A.length;
        
        for(int i=0; i < len ; ++i) {
            if(A[i] == leader.value) {
                ++leaderCounter;                
            }
            if ((leaderCounter > (i+1)/2 && (leader.ocurrences - leaderCounter)>(len-1-i)/2) ) {
                ++equileaders;
            }
        }        
        return equileaders;
    }
    
    public static class Leader {
        int ocurrences;
        int value;
        
        public Leader(int value, int ocurrences) {
            this.value = value;
            this.ocurrences = ocurrences;
        }
    }
    
    public Leader getLeader(int[] A) {
        int indexOfCandidate = -1;
        int stackCounter = 0, candidate=-1, value=-1, i =0;

        for(int element: A ) {
            if (stackCounter == 0) {
                value = element;
                ++stackCounter;
                indexOfCandidate = i;
            } else {
                if (value == element) {
                    ++stackCounter;
                } else {
                    --stackCounter;
                }
            }
            ++i;
        }

        if (stackCounter > 0 ) {
            candidate = value;
        } else {
            return null;
        }

        int countRepetitions = 0;
        for (int element: A) {
            if( element == candidate) {
                ++countRepetitions;
            }
        }
        
        if(countRepetitions > (A.length / 2)) {            
            return new Leader(candidate, countRepetitions);
        }
        return null;
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example
example test

✔

1.334 s

expand all Correctness tests

▶

single
single element

✔

1.332 s

1.324 s

1.331 s

▶

double
two elements

✔

1.345 s

1.319 s

1.331 s

▶

simple
simple test

✔

1.341 s

1.321 s

▶

small_random
small random test with two values, length = ~100

✔

1.323 s

▶

small
random + 200 * [MIN_INT] + random ,length = ~300

✔

1.331 s

expand all Performance tests

▶

large_random
large random test with two values, length = ~50,000

✔

1.421 s

▶

large
random(0,1) + 50000 * [0] + random(0, 1), length = ~100,000

✔

1.484 s

▶

large_range
1, 2, ..., N, length = ~100,000

✔

1.569 s

1.335 s

▶

extreme_large
all the same values

✔

1.695 s