Solution to Count-Non-Divisible by codility

28 Jan


Question Name: CountNonDivisible

12 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…

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

  4. 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:

    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.

  5. My solution in C++ (100%):

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!