##### Short Problem Definition:

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

##### Link

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

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.

##### Solution:

def solution(A): A_max = max(A) count = {} for element in A: if element not in count: count[element] = 1 else: 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]: divisors[element_candidate].add(divisor) divisors[element_candidate].add(element_candidate//divisor) 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

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.