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
    }

  • BruceFromSeattle

    100% correct, 100% performance; in C# (sorry)

    static int[] solution(int[] A) // time complexity O(N*log(N)), space complexity O(N)
    {
    int nIntCount = A.Length; // = N in problem statement
    int nMaxInt = nIntCount + nIntCount; // max possible input int; problem statement specifies this
    int[] anIntCounts = new int[nMaxInt + 1]; // array of counters for all possible input ints
    // (plus a never-used counter for 0)
    int[] anDivisorCounts = new int[nMaxInt + 1]; // array of counters for counts of divisors
    int[] anNotDivCounts = new int[nIntCount]; // to be returned, length and order same as input array A
    foreach (int a in A) // transform input array A into counts of its ints
    anIntCounts[a]++;
    for (int i = 0; i 0) // skip this iteration if input array A didn’t have this int
    for (int im = i; im <= nMaxInt; im += i) // mark multiples (they're divisable by this int, of course)
    // since we're in the Sieve of Eratosthenes lesson
    anDivisorCounts[im] += anIntCounts[i]; // mark by storing input int counts
    // (some counts will never be read)
    for (int i = 0; i < nIntCount; i++)
    anNotDivCounts[i] = nIntCount – anDivisorCounts[A[i]]; // compute counts of non-divisors
    // (in original order of input array A)
    return anNotDivCounts;
    }

  • Sir Harry Plunket-Greene

    // short and sweet in C++
    vector solution(vector &A)
    {
    int N = A.size(), M = 2*N+1;
    vector occurs(M, 0), nondiv(M, N), result;

    for (int a: A) occurs[a]++;
    for (int i=1; i<M; i++) if (occurs[i]) for (int j=i; j<M; j+=i) nondiv[j] -= occurs[i];
    for (int a: A) result.push_back(nondiv[a]);
    return result;
    }