Solution to Dominator by codility

24 Jan

Question: http://codility.com/demo/take-sample-test/dominator

Question Name: Dominator

Same question in the introduction pdf.

21 Replies to “Solution to Dominator by codility

  1. Hey Sheng,

    as I was reading this task I misread it and came up with a really tough problem. I would be interested in your ideas.

    What is the leading denominator in a sequence of numbers (the number that divides more than half the array entries)?

    There are roughly 200 milion primes in an integer. The rest would be the same.

    Have you seen a similar problem somewhere? Any great ideas how to solve it :)?

    • I did not test it. But if 1 is permitted, 1 is the leading denominator.

      If 1 is not counted, and the sequence of numbers are continue (from 1 to som number, like 1 – 2 -3 -4 -5 -6), 2 would be in most case.

      In other cases, we have to compute the denominator for each number.

      PS: Better solution might exist. But I do not know~. If you get it, please tell me!

    • Yes and no. Yes, literally we can avoid loops by using Counter. No, essentially, with or without Counter, our program is going to iterate all the items.

  2. Solution in Java

  3. Here’s a simple C implementation for which I scored 100% on codility:

  4. C#, 100%. Because of the Dictionary its time complexity detected as O(N) or O(N*log(N))

  5. A Java solution without using a HashMap, based on the introductory lecture for the lesson ( I read it and then after understanding the lecture I started the implementation).

  6. Here’s my first solution in PHP 100% 😀

  7. Like Martin, I also misunderstood the demand at first but this is also a way to improve. Anyway, here’s my solution, and it is O(2*log(N)) instead of O(N) as demanded thanks to sorted (once) and bisect (twice but each time over N/2).

    https://codility.com/demo/results/trainingVJESZY-PDW/

  8. This is a very interesting idea. The main point lies in that a dominator has to appear more than half of the total number of elements in the list. Wonderful. Is there a rigorous proof for this?

  9. Hi Sheng,

    May I share my python solution? Got 100% in O(N). Any thoughts?

  10. Hi Sheng,

    I think your code does not meet the space complexity, because this line:

    creates an array so it is no o(1) complexity or am I wrong?,

    Thanks,

    • You are absolutely right. That code uses O(N) space, while you are easily reduce the space usage to O(1)-space by an O(N)-time traversal. Thanks!

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!