CountNonDivisible - Codility training task

Question

I'm traning on codility now. Some tasks I can solve by myself, but with some tasks have problems. Difficulty of this task is <**>. It's medium, but I stalled.

Problem:

---

You are given a non-empty zero-indexed 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[6] = 6, there aren't any non-divisors.

Write a function:

class Solution { public int[] solution(int[] A); }

that, given a non-empty zero-indexed array A consisting of N integers, returns a sequence of integers representing the numbers of non-divisors. The sequence should be returned as:

• a structure Results (in C),
• or a vector of integers (in C++),
• or a record Results (in Pascal),
• or an array of integers (in any other programming language).

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. Assume that:

• N is an integer within the range [1..50,000];
• each element of array A is an integer within the range [1..2 * N].

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

---

I have written some solutions. But my solutions bulky and still have O(n^2) complexity. Can you help me with some ideas or algorithms how to do it optimally? It's not an interview task or something else. I'm just training and try to solve all tasks. You can find this task here: http://codility.com/demo/train/ Lesson 9, first task in lesson.

Thank you!

Answer 1

I thought I'll share my solution in C++ which gets 100 score. I think it's pretty straightforward.

https://codility.com/demo/results/demoQFK5R5-YGD/

1. First it counts the occurrences of each number in the array.

2. Then for each array element i it finds the number of its divisors in a range from 1 to sqrt(i), including the divisors which are the result of the division.

3. Finally it subtracts a total number of divisors for given element from a total number of elements in the array.

   vector<int> solution(vector<int> &A) {
   
       int N = A.size();
       vector<int> counts (*std::max_element(A.begin(), A.end()) + 1,0);
   
       // Calculate occurences of each number in the array
       for (int i = 0; i < N; ++i)
       {
           counts[A[i]] += 1;
       }
   
       std::vector<int> answer(N,0);
   
       // For each element of the array
       for (int i = 0; i < N; ++i)
       {
           // Calulate how many of its divisors are in the array
           int divisors = 0;
   
           for (int j = 1; j * j <= A[i]; ++j)
           {
               if (A[i] % j == 0)
               {
                   divisors += counts[j];
                   if (A[i] / j != j)
                   {
                       divisors += counts[A[i] / j];
                   }
               }
           }
   
           // Subtract the number of divisors from the number of elements in the array
           answer[i] = N - divisors;
       }
   
       return answer;
   }