Codility 'CountNonDivisible' Solution

Martin Kysel · January 5, 2015

Short Problem Definition:

Calculate the number of elements of an array that are not divisors of each element.



expected worst-case time complexity is O(N\*log(N))

expected worst-case space complexity is O(N)


Using the Sieve of Eratosthenes, you generate divisors for all input elements of A. If a given number x is a divisor of element (x*N == element), then N also is a divisor. (N = element//x). After all divisors are computed, we simply subtract those (multiplied by their counts or 0) from the total number of elements in A.


def solution(A):
    A_max = max(A)
    count = {}
    for element in A:
        if element not in count:
            count[element] = 1
            count[element] += 1
    divisors = {}
    for element in A:
        divisors[element] = set([1, element])
    # start the Sieve of Eratosthenes
    divisor = 2
    while divisor*divisor <= A_max:
        element_candidate = divisor
        while element_candidate  <= A_max:
            if element_candidate in divisors and not divisor in divisors[element_candidate]:
            element_candidate += divisor
        divisor += 1
    result = [0] * len(A)
    for idx, element in enumerate(A):
        result[idx] = (len(A)-sum([count.get(divisor,0) for divisor in divisors[element]]))
    return result

Twitter, Facebook