Problem

You are given an array A consisting of N integers. 

For each number A[i] such that 0 <= i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.

For example, consider integer N = 5 and array A such that: 

    A[0] = 3

    A[1] = 1

    A[2] = 2

    A[3] = 3

    A[4] = 6

For the following elements: 

        A[0] = 3, the non-divisors are: 2, 6,

        A[1] = 1, the non-divisors are: 3, 2, 3, 6,

        A[2] = 2, the non-divisors are: 3, 3, 6,

        A[3] = 3, the non-divisors are: 2, 6,

        A[4] = 6, there aren't any non-divisors.

Write a function: 

    vector<int> solution(vector<int> &A);

that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors. 

Result array should be returned as an array of integers.

For example, given: 

    A[0] = 3

    A[1] = 1

    A[2] = 2

    A[3] = 3

    A[4] = 6

the function should return [2, 4, 3, 2, 0], as explained above. 

Write an efficient algorithm for the following assumptions:

·         N is an integer within the range [1..50,000];

·         each element of array A is an integer within the range [1..2 * N]. 

Note:

“non-divisors” means “non-factors”.

With the given array, the non-divisors for A[0] are 2 and 6, and so the first element of the return vector is 2, for counting the two numbers, 2 and 6. The non-divisors for A[1] = 1 are: 3, 2, 3, and 6, with 3 occurring two times; and so the second element of the return vector is 4, for counting the four numbers, 3, 2, 3, and 6. The non-divisors for A[2] = 2 are: 3, 3, 6 with 3 occurring two times, and so the third element of the return vector is 3, for counting the three numbers, 3, 3, and 6. The non-divisors for A[3] = 3 are: 2 and 6, and so the fourth element of the return vector is 2, for counting the two numbers, 2 and 6. Non-divisors for A[4] = 6 do not occur, and so the fifth element of the return vector is 0. 

Illustration

The given dataset is

    3, 1, 2, 3, 6 

Sorting this list ascending gives:

    1, 2, 3, 3, 6 

With this sorted list, it is easy to see that the non-divisors for 1 are all the elements above 1, which are 2, 3, 3, 6. With this sorted list, it is also easy to see that the non-divisors for 2 are all the elements above 2, which are 3, 3, 6. That is not all.

Any integer that is above the integer in question, is a non-divisor. Still, in the case of 3, six is a non-divisor. However, 2 which is less than 3 is also a non-divisor for 3 (three cannot divide 2 without a remainder).

In the case of 6, there is no integer above 6. All the integers below 6, and including 6 itself are factors (divisors) of 6, and there is no non-divisor below 6.

The strategy is to be able to count the divisors (factors) below and including the integer in question, and then subtract that number from the total number, N, which in this case is 5.

The dataset (list) is given as follows:

    3, 1, 2, 3, 6

The divisors for 3 are 1, 3 and 3, making 3 numbers. 5 - 3 = 2, which is the number of non-divisors for 3. The divisors for 1 are 1 alone, making 1 number. 5 - 1 = 4, the number of non-divisors for 1. The divisors for 2 are 1 and 2, making 2 numbers. 5 - 2 = 3, the number of non-divisors for 2.

The divisors for 6 are 1, 2, 3 and 3, and 6 itself, making 5 numbers. 5 - 5 = 0, which is the number of non-divisors for 6. 

With all that, the result is: [2, 4, 3, 2, 0]

What kind of Sorting?

Sorting is necessary in the solution. So, what kind of sorting? If merge-sort is used, the sorting process would likely be fastest, but the result will not indicate the number of occurrences of an integer in the given list. On the other-hand, though counting sort is slower than merge-sort, counting sort will indicate the presence or absence of an integer (value) in the given list, and will also indicate the number of occurrence of an integer (value) in the given list. So, counting sort is chosen.

The Count Sort Vector

The count sort vector for the given data list (3, 1, 2, 3, 6) is as follows:

Algorithm

The algorithm for the smart solution function is as follows:

- Develop the count sort array. Remember that the number of elements for the counting sort array (count) is N + 1, for the possibility of 0 in the given list. The maximum integer is m, which is the biggest number in the given list. In this case, m is 2xN as given in the following assumption in the problem:

·         each element of array A is an integer within the range [1..2 * N].

- Next, determine the number of factors (divisors) for each integer in the given list, using the count sort array, and then subtract that count from N. In determining the factors (divisors), both corresponding factors on either side of A[i] in the given list, have to be considered. Remember that A[i] itself, is a factor (divisor) for itself.

Smart Solution

A solution() function is in the following program (read the code and comments):

#include <iostream> 
#include <vector>
using namespace std;

vector<int> solution(vector<int> &A) {
    int N = A.size();
    vector<int> result(N);
    vector<int> cntSortV(2*N+1, 0);

    for (int i=0; i<N; i++) {
        cntSortV[A[i]] += 1;  //add 1 for each occurrence
    }

    for (int i=0; i<N; i++) {
        int j = 1;    //because 0 cannot be a divisor
        int ctr = 0;  //number of divisors per element
        while (j*j < A[i]) {    //j is from 1 to sqrt of A[i] 
            if (A[i] % j == 0) {
                //check presence of both divisors about sqrt of A[i]
                if (cntSortV[j] > 0)    //if j is a member of A and is an index in cntSortV[j]
                    ctr = ctr + cntSortV[j];
                int higher = A[i] / j;    //higher is corresponding divisor above sqrt of A[i]
                if (cntSortV[higher] > 0)
                    ctr = ctr + cntSortV[higher];
            }
            j = j + 1;
        }
        if (j * j == A[i]) {//perfect square
            if (cntSortV[j] > 0)
                ctr = ctr + cntSortV[j];
        }
        result[i] = N - ctr;  //asked for non-divisors
    }

    return result;
}

int main(int argc, char **argv) 
{ 
    vector<int> B{3, 1, 2, 3, 6};

    vector<int> ret = solution(B);

    for(int k=0;k<ret.size();k++)
        cout << ret[k] << ' ';
    cout << endl;

    return 0; 
}

The output is: 

    2 4 3 2 0

The reader should mentally run (without executing) all the elements, A[i] of the given array, through the solution() function, in order to really appreciate the operation of the function. 

At app.codility.com/programmers the scoring and detected time complexity for this solution() is:

    Task score : 88% -  Correctness : 100% ; Performance : 75%

    Detected time complexity : O(N * log(N)) or O(N²) 

Why is performance not 100% ? The performance error is as follows

Analysis summary

The following issues have been detected: timeout errors. 

The solution() function took 0.100 secs and the time limit required is 0.100 secs.