Question: https://codility.com/demo/take-sample-test/count_non_divisible
Question Name: CountNonDivisible
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 35 36 37 | def solution(A): from math import sqrt A_max = max(A) A_len = len(A) # Compute the frequency of occurrence of each # element in array A count = {} for element in A: count[element] = count.get(element,0)+1 # Compute the divisors for each element in A divisors = {} for element in A: # Every nature number has a divisor 1. divisors[element] = [1] # In this for loop, we only find out all the # divisors less than sqrt(A_max), with brute # force method. for divisor in xrange(2, int(sqrt(A_max))+1): multiple = divisor while multiple <= A_max: if multiple in divisors and not divisor in divisors[multiple]: divisors[multiple].append(divisor) multiple += divisor # In this loop, we compute all the divisors # greater than sqrt(A_max), filter out some # duplicate ones, and combine them. for element in divisors: temp = [element/div for div in divisors[element]] # Filter out the duplicate divisors temp = [item for item in temp if item not in divisors[element]] divisors[element].extend(temp) # The result of each number should be, the array length minus # the total number of occurances of its divisors. result = [] for element in A: result.append(A_len-sum([count.get(div,0) for div in divisors[element]])) return result |
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?
I do not know neither~ But I agree with you about the time complexity.
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.
I do not know how to prove it. But my solution should also be O(N* logN).
https://codility.com/media/train/9-Sieve.pdf
I ‘m not sure that A_max = max(A) costs less than it helps, compare to 2 * N, where it’s used.
O(2 * N) equals to O(N). Essentially max(A) does not increase the overall complexity.
Hi Sheng,
You have a really good solution to all the problems. I always check on your solutions after trying my own. For this particular problem I have a very similar solution to yours but mine is failing for some test cases. If possible can you point me the mistake?
https://codility.com/demo/results/demoB54VPZ-3P6/
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.
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).
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: https://app.codility.com/demo/results/trainingK4K7C2-SZ9/
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.
My solution in C++ (100%): https://app.codility.com/demo/results/training8RPPG3-J6P/