Question: http://codility.com/demo/take-sample-test/dominator
Question Name: Dominator
Same question in the introduction pdf.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def solution(A): A_len = len(A) candidate = -1 candidate_count = 0 candidate_index = -1 for index in xrange(A_len): if candidate_count == 0: candidate = A[index] candidate_index = index candidate_count += 1 else: if A[index] == candidate: candidate_count += 1 else: candidate_count -= 1 if len([number for number in A if number == candidate]) <= A_len//2: return -1 else: return candidate_index |
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!
Hi there.
One trick to avoid loops here is to use Counter from collections.
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.
Solution in Java
Correct, but you could break in the second if statement.
Hi! I was wondering does HashMap provide required memory complexity O(1). For me it doesn’t as we can create HashMap with N entries if each entry is different.
Did not notice the space requirement. Yes, you are totally right. This solution does not meet the space requirement.
Here’s a simple C implementation for which I scored 100% on codility:
C#, 100%. Because of the Dictionary its time complexity detected as O(N) or O(N*log(N))
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).
Here’s my first solution in PHP 100% 😀
Hereby I send my solution to this task in JAVA
https://codility.com/demo/results/trainingY7492E-D6X/
If you think I could done it better please dont hesitate to comment.
Thanks
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/
It should be your typo. Its complexity is O(N * log(N)), not O(2*log(N)).
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?
By the definition in the question statement.
Hi Sheng,
May I share my python solution? Got 100% in O(N). Any thoughts?
It should be correct. But it does not meet the space complexity requirement of the problem.
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!
It seems that your code generates 6 instead of 3, and 0 instead of 1, respectively for:
All functions from PDF (i.e. slowLeader, fastLeader and goldenLeader) give the results: 3 and 1. I am not sure, cause I have not analyzed your code very carefully, but shouldn’t the last line of code be changed to:
or just
Now it works fine. Solution should return found dominator, not its index.
The PDF has some similar questions, but not the same. The original question description says “returns index of any element of array A in which the dominator of A occurs”.
You are right. This is specified in the leading description of the Dominator task ( https://goo.gl/t7YDqi ). I have been misleaded by functions in codility lessons and this text “The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.” But this is obviouos after reading such statement: “the function may return 0, 2, 4, 6 or 7, as explained above”. Probably automatic testing checks whether the result belongs to the given set of indexes or not. It is interesting that the specific result mainly depends on the implementation. There is no strict requirement for that, let’s say: first or last index. OK, that is clear now.
Nevertheless, thanks for your blog. I have learned a lot from published Python solutions (in posts and comments). Some of the used approaches to solve problems are realy brilliant and tricky, in order to meet complexity expectations. I have already run them all in Eclipse. Tens of files 🙂 Now I want to do the same with Java versions 😉
C# 100% with little bit Linq
my python solution 🙂
Could you post your score. It looks like it would be O(N^2) because you have a “in” inside a for loop.
Here is my solution which got 100% with time complexity O(N).
Here’s my solution
Python solution using collections.Counter
Strange thing is: codility explains Leader as “The leader of this sequence is the element whose value occurs more than n/2 times”. But isn’t it actually when element is more then sum of elements on right side?
100% on codility