Codility ‘CountNonDivisible’ Solution

Short Problem Definition:

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

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]:
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.

• 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;
}