Solution to Count-Non-Divisible by codility

28 Jan


Question Name: CountNonDivisible

9 Replies to “Solution to Count-Non-Divisible by codility

  1. 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?

  2. 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.

    • 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.

  3. 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…

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!