# Solution to Count-Non-Divisible by codility

28 Jan

Question Name: CountNonDivisible

### 12 Replies to “Solution to Count-Non-Divisible by codility”

1. Julian says:

I wonder why this exercise is in the “Sieve of Eratosthenes”, since it’s about divisors (as opposed to factors). Related to this, the detected complexity of my 100% solution was

, when it really was

, which I suspect holds for your solution as well. Thoughts?

• Sheng says:

I do not know neither~ But I agree with you about the time complexity.

2. Andrew says:

Here is a solution that uses a prime number sieve that I believe runs in O(n * log n). Unfortunately, the code is much more complex than the neat O(n^3/2) solution posted above.
The idea is to use a sieve to find the smallest prime that divides each number in the input range, from which one can determine the prime factorization of each number in the input range (this method is described in the reading material that accompanies these questions). Given the prime factorization of x, one can obtain a complete list of divisors of x which is used in the same way as your code above.
I’d love to see the author’s intended solution for this question.

• Pierre-Yves says:

I ‘m not sure that A_max = max(A) costs less than it helps, compare to 2 * N, where it’s used.

• Sheng says:

O(2 * N) equals to O(N). Essentially max(A) does not increase the overall complexity.

3. Anu says:

Hi Sheng,
You have a really good solution to all the problems. I always check on your solutions after trying my own. For this particular problem I have a very similar solution to yours but mine is failing for some test cases. If possible can you point me the mistake?
https://codility.com/demo/results/demoB54VPZ-3P6/

• Sheng says:

Sorry, I do not know much about the C#. But you could use “Console.WriteLine(“this is a debug message”);” to print out all the elements of input A. Then you could debug locally and find out the bug.

4. micropentium6 says:

Here goes my dummy solution! I can prove it’s O(NlogN) though. Since the inner loop runs N times, and each run, it has: sqrt(2)*log2, sqrt(3)*log3…sqrt(N)*logN < (sqrt(2)+sqrt(3)+…+sqrt(N))*logN <= NlogN
The solution is ugly. Take a look on how much extra space I took! It's still considered as O(N) though…

• Vajda Akos says:

Dear micropentium6,
thanks so much for your solution, it helped me a lot to understand the exercise!

I slightly improved your solution and now it is detected O(N * log(N))

The only major difference is the initialization of the sortedA and result1 vectors, where I avoided the unnecessary copies. The others are only code style, it is slightly more readable (well, for me anyway).

5. Mehulkumar says:

Hi Sheng! Here’s my solution. It’s somewhat similar to your idea of using sieve to find divisors. As per the reading document they provide, the attached solution should run in no more than O(n log log n). Solution is in go.

Here’s the result: https://app.codility.com/demo/results/trainingK4K7C2-SZ9/

I see that your nested loop starts with ‘divisor’ and in that loop it checks for duplicate ‘multiple’ in an array if I’m not wrong. Those things seems increasing the overall time/space complexity of your solution.

Hope anyone find this useful in the future. Thanks.

6. Luiz doleron says:

My solution in C++ (100%): https://app.codility.com/demo/results/training8RPPG3-J6P/