Codility ‘CountNonDivisible’ Solution

Short Problem Definition:

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

Link

CountNonDivisible

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Nico

    Any solution in C?

    Here is mine, but must be an easier one… I did not get any performance point… and it is a too large and ugly code… I needed a debugger to make it work… :/ How would you implement the divisors diccionary in C ?

    https://codility.com/demo/results/trainingDEVNBN-RCR/

    • Ajay saini

      #include
      #include
      #include
      #include
      #include
      #include
      #include

      int main(){
      int Alice=0,Bob=0,i;
      int a[3],b[3];
      for(i=0;i<3;i++)
      scanf("%d ",&a[i]);

      for(i=0;i<3;i++)
      scanf("%d ",&b[i]);
      for(i=0;i<3;i++)
      {
      if(a[i]b[i])
      {
      Bob+=1;
      }
      }
      printf(“%d %d”,Bob,Alice);
      return 0;
      }

  • Michiel van der Blonk

    Here’s my javascript solution, short and sweet.
    https://codility.com/demo/results/trainingCHR3DB-JCA/

  • son phuong

    solution in Scala 71% in codility

    def solution(a: Array[Int]): Array[Int] = {
    val arrTemp = scala.collection.mutable.ListBuffer.empty[Int]
    val arrSize = a.length
    var i,j,n = 0
    while(i < arrSize){
    n= 0
    j = 0
    while(j < arrSize){
    if(a(i) % a(j) == 0) n += 1
    j += 1
    }
    arrTemp += arrSize – n
    i += 1
    }
    arrTemp.toArray
    }