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:

def solution(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 Python

Time spent on task 5 minutes

Notes

not defined yet

Task timeline

Code: 01:18:44 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// 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
    }
}

Code: 01:19:00 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    pass

Code: 01:19:07 UTC, py, autosave

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
            if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
                Sum += 1
    return Sum

Code: 01:19:37 UTC, py, autosave

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
            if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
                Sum += 1
    return Sum

Code: 01:19:47 UTC, py, autosave

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
            if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
                Sum += 1
    return Sum

Code: 01:20:25 UTC, py, autosave

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
            p
            if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
                Sum += 1
    return Sum

Code: 01:20:37 UTC, py, autosave

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
            print(curNum, i, num, leader)
            if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
                Sum += 1
    return Sum

Code: 01:20:37 UTC, py, 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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
            print(curNum, i, num, leader)
            if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
                Sum += 1
    return Sum

User test case 1:

[4, 4, 2, 5, 3, 4, 4, 4]

Analysis

expand all Example tests

▶

example
example test

✔

0.036 s

stdout:

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 2

stdout:

Code: 01:21:06 UTC, py, 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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
            print(curNum, i, num, leader, Sum)
            if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
                Sum += 1
    return Sum

User test case 1:

[4, 4, 2, 5, 3, 4, 4, 4]

Analysis

expand all Example tests

▶

example
example test

✔

0.056 s

stdout:

expand all User tests

▶

test_data1

✔

0.060 s

OK
function result: 2

stdout:

Code: 01:23:00 UTC, py, autosave

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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
            print(curNum, i, num, leader, Sum)
        if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
                Sum += 1
    return Sum

Code: 01:23:10 UTC, py, 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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
        if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
            Sum += 1
    return Sum

User test case 1:

[4, 4, 2, 5, 3, 4, 4, 4]

Analysis

expand all Example tests

▶

example
example test

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 3

Code: 01:23:31 UTC, py, 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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
        if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
            Sum += 1
    return Sum

User test case 1:

[4, 4, 2, 5, 3, 4, 4, 4]

Analysis

expand all Example tests

▶

example
example test

✔

0.036 s

expand all User tests

▶

test_data1

✔

0.036 s

OK
function result: 3

Code: 01:23:33 UTC, py, 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

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
        if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
            Sum += 1
    return Sum

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example
example test

✔

0.036 s

expand all Correctness tests

▶

single
single element

✔

0.036 s

▶

double
two elements

✔

0.036 s

▶

simple
simple test

✔

0.040 s

0.036 s

▶

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

✔

0.036 s

▶

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

✔

0.036 s

expand all Performance tests

▶

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

✔

0.112 s

▶

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

✔

0.176 s

▶

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

✔

0.144 s

0.036 s

▶

extreme_large
all the same values

✔

0.184 s