Question: http://codility.com/demo/take-sample-test/equi_leader
Question Name: EquiLeader
A variant of the previous question.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | def solution(A): A_len = len(A) candidate = -1 candidate_count = 0 candidate_index = -1 # Find out a leader candidate 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 # Make sure the candidate is the leader leader_count = len([number for number in A if number == candidate]) if leader_count <= A_len//2: # The candidate is not the leader return 0 else: leader = candidate equi_leaders = 0 leader_count_so_far = 0 for index in xrange(A_len): if A[index] == leader: leader_count_so_far += 1 if leader_count_so_far > (index+1)//2 and leader_count-leader_count_so_far > (A_len-index-1)//2: # Both the head and tail have leaders of the same value # as "leader" equi_leaders += 1 return equi_leaders |
Here’s my java solution, uses O(1) space.
https://codility.com/demo/results/demoGWVETC-3SD/
Thanks for sharing your solution!
Nice and clean ! But when i try with [1,2,1,2,1,2,1,2,3,1] it gave “value” as 3 instead of 1.
Well~ I tried and it returned 0 for [1,2,1,2,1,2,1,2,3,1].
Solution in c# :
https://codility.com/demo/results/demoJ6VXA6-SYF/
Thank you for providing the solution in another language!
Here’s my C solution :
thanks. easy to read.
Thanks for putting this solution together.
Your tidy code along with the comments was the first solution that helped me understand how this problem is solved.
Adding my Java Solution 100/100
https://codility.com/demo/results/demoZSME5G-RXN/
Well, again, I was numb to recognize the fact equileader exists if and only if it is the leader of the sequence. Fortunately, codility is kind this time and allows space complexity to be O(N). This gives me the opportunity to apply the old hashtable trick here. An extra vector is needed to store the leader-end-here. And then scan the sequence backward to find the leader starting from N-1 to 1, so we can compare the backward leader with the leader-end-here saved in the vector.
I have to admit my solution is silly though…
Sheng, alternatively, you can detect leader by comparing candidate_count > 0, if it is true, then candidate is definitely a leader, otherwise there is no leader in array.
No, you cannot. Consider the input [1, 2, 3, 4, 5, 5].
You are right: Python might be slow, but it really makes my code shorter…Well, comparing with the dummy solution I submitted last year ^_^
It is amazing how programmers approach the same problem differently.
here is my solution:
https://codility.com/demo/results/trainingUQ5UYH-QTT/
Thanks Sheng for this nice blog. 👍
This has O(N**2) complexity
My solution in python.
https://app.codility.com/demo/results/trainingCBEVUP-QXR/
my solution(A):
My solution in Python, with comments: