Lesson 9: CountNonDivisible (Count Non Divisible)

Lesson 9: CountNonDivisible
https://codility.com/programmers/lessons/9


(1) The O(N * sqrt(N)) solution 

The simplest solution is to check the occurrences of each value first, and then when we we given a number A[i], we check the divisors of A[i], which will be between 1 and sqrt(A[i]).  We count the total number of the occurrences of all the divisors (and the answers for (A[i] / divisor) ) and and subtract it from N.

This solution gives the 100% score.

However, the time complexity of the part to check a number between 1 and sqrt(A[i]) is O(sqrt(N)) , so this is indeed O(N * sqrt(N)), while the problem requires a O(N * log(N) ) solution. 

I have to find another solution for this. 

I just googled and found that many people indeed just implement this O(N * sqrt(N)) solution. However, I found one Chinese guy implements O(N * log(N) ) solution in C++, here.

The next section implements his strategy but with a slight improvement.  

#include<alloca.h>
#include<memory.h>

struct Results solution(int A[], int N) 
{
    //the number that may appear will be [1 ... 2 * N].
    int size = sizeof(int) * (N * 2 + 1);    
    int* occurrence = (int*)alloca(size);
    memset(occurrence, 0x00, size);
        
    
    //allocate the memory for the result.
    struct Results result;
    result.C = (int*)calloc(N, sizeof(int));
    result.L = N;
        
    //now we check the array A and count the occurance for each number.
    int i,j;
    for (i = 0; i < N; i++){
        occurrence[A[i]]++;
    }
          
    //now we compute the answer.
    for (i = 0; i < N; i++){
        int num = A[i];

        int div_cnt = 0;
        
        //count the number of the divisor while doing factorization.
        for (j = 1; j * j < num; j++){
            if (num % j == 0){
                div_cnt += occurrence[j];
                div_cnt += occurrence[num / j];
            }
        };
        
        if (j * j == num){
            div_cnt += occurrence[j];
        }
        
        result.C[i] = N - div_cnt;
    }
    
    return result;
}


(2) The O(N * log(N)) solution 

Here is the O(N * log(N)) solution. 

First, we check how many times each number between 1 to N * 2 appears in the array A. This is the same as the previous O(N * sqrt(N)) solution. This can be done by scanning the array A and the time complexity is O(N). 

The difference from the previous solution is as follows.
We then check each number between 1 to N * 2.

First we prepare the answer array, so to store the answer for a number `i' at its cell, answer[i]. So by looking up answer[i], we can have the answer for the number 'i' by a constant time.

For now, we assume, for all the numbers from 1 to N * 2,  N is the answer, which means we temporarily assume that there is no divisor in the array A for any number. We will compute the correct answer from now on, by subtracting the occurrences of its divisors. 

Now we scan the occurrence array to check from head to tail.
If the number that we are currently scanning occurs, then we subtract its number of occurrence from the location of its multipliers.

For example if we are currently checking the number '3' and its occurrence in the array A is twice, we subtract 2 from answer[3], answer[6], answer[9], answer[12]. This means that we are subtracting the occurrence of 3 from these numbers of multiples of 3. 

By repeating this from 1 to N * 2, we can compute the number of the non-divisors of each number in the range.

As, we saw in Lesson 8: Prime Numbers, the time complexity of this algorithm is  O(N * log (N)). (See Reversing coins, Lesson 8: Open reading material (PDF) ).

Since the first scan to check the occurrences of each number is O(N) the above algorithm is O(N * log(N)). When these parts are combined it is O(N * log(N) ) time complexity. The look up from the answer table is in a constant time and must be repeated for N times, it is O(N).

Thus, the whole time complexity of the below code is O(N * log(N)), as the problem is required.

#include<alloca.h>
#include<memory.h>

struct Results solution(int A[], int N) 
{
    //the number that may appear will be [1 ... 2 * N].
    int size = sizeof(int) * (N * 2 + 1);    
    int* occurrence = (int*)alloca(size);
    memset(occurrence, 0x00, size);
    
    //the space to hold the answer for each value from 1 ... 2 * N.
    //for now we initialize it 
    int* answer = (int*)alloca(size);
    memset(answer, 0x00, size);
    
    
    //allocate the memory for the result.
    struct Results result;
    result.C = (int*)calloc(N, sizeof(int));
    result.L = N;
        
    //now we check the array A and count the occurance for each number.
    int i;
    for (i = 0; i < N; i++){
        occurrence[A[i]]++;
    }
        
    //now we compute the answer.
    for (i = 1; i <= N * 2; i++){
        int num = occurrence[i];
        
        //the number doesn't in the array A, we can neglect it.
        if (num == 0){
            continue;
        }

        //if it appears in the array A, 
        //subtract its counts from cells at itss multiples in the answer array.
        int j;
        for (j = i; j <= N * 2; j += i){
            answer[j] -= num;
        }        
    }
    
    //as the answer array contains the offset to N, 
    //N + answer[A[i]] will give the answer for each.
    for (i = 0; i < N; i++){
        result.C[i] = N + answer[A[i]];
    }
    
    return result;
}