Tasks Details
medium
Calculate the number of elements of an array that are not divisors of each element.
Task Score
100%
Correctness
100%
Performance
100%
You are given an array A consisting of N integers.
For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.
For example, consider integer N = 5 and array A such that:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6For the following elements:
- A[0] = 3, the non-divisors are: 2, 6,
- A[1] = 1, the non-divisors are: 3, 2, 3, 6,
- A[2] = 2, the non-divisors are: 3, 3, 6,
- A[3] = 3, the non-divisors are: 2, 6,
- A[4] = 6, there aren't any non-divisors.
Write a function:
def solution(A)
that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.
Result array should be returned as an array of integers.
For example, given:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6the function should return [2, 4, 3, 2, 0], as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..50,000];
- each element of array A is an integer within the range [1..2 * N].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 2 minutes
Notes
not defined yet
Task timeline
Code: 09:51:32 UTC,
java,
autosave
Code: 09:51:52 UTC,
py,
autosave
import collections
import math
def solution(A):
num_hash = collections.defaultdict(int)
answer_hash = collections.defaultdict(int)
length = 0
for num in A:
num_hash[num] += 1
length += 1
answer = []
for num in A:
#print("num ::: " + str(num))
if answer_hash[num] != 0:
answer.append(answer_hash[num])
continue
count = 0
for measure in range(1, math.floor(num ** (1/2)) + 1):
#print("measure ::: " + str(measure))
if num % measure != 0:
continue
count += num_hash[measure]
if measure * measure != num:
count += num_hash[num // measure]
#print("num // measure ::: " + str(num // measure))
#print("count ::: " + str(count))
answer_hash[num] = length - count
answer.append(length - count)
#print(answer)
return answer
Code: 09:52:03 UTC,
py,
autosave
import collections
import math
def solution(A):
num_hash = collections.defaultdict(int)
answer_hash = collections.defaultdict(lambda : -1)
length = 0
for num in A:
num_hash[num] += 1
length += 1
answer = []
for num in A:
#print("num ::: " + str(num))
if answer_hash[num] != 0:
answer.append(answer_hash[num])
continue
count = 0
for measure in range(1, math.floor(num ** (1/2)) + 1):
#print("measure ::: " + str(measure))
if num % measure != 0:
continue
count += num_hash[measure]
if measure * measure != num:
count += num_hash[num // measure]
#print("num // measure ::: " + str(num // measure))
#print("count ::: " + str(count))
answer_hash[num] = length - count
answer.append(length - count)
#print(answer)
return answer
Code: 09:52:16 UTC,
py,
autosave
import collections
import math
def solution(A):
num_hash = collections.defaultdict(int)
answer_hash = collections.defaultdict(lambda : -1)
length = 0
for num in A:
num_hash[num] += 1
length += 1
answer = []
for num in A:
#print("num ::: " + str(num))
if answer_hash[num] != -1:
answer.append(answer_hash[num])
continue
count = 0
for measure in range(1, math.floor(num ** (1/2)) + 1):
#print("measure ::: " + str(measure))
if num % measure != 0:
continue
count += num_hash[measure]
if measure * measure != num:
count += num_hash[num // measure]
#print("num // measure ::: " + str(num // measure))
#print("count ::: " + str(count))
answer_hash[num] = length - count
answer.append(length - count)
#print(answer)
return answer
Code: 09:52:25 UTC,
py,
verify,
result: Passed
import collections
import math
def solution(A):
num_hash = collections.defaultdict(int)
answer_hash = collections.defaultdict(lambda : -1)
length = 0
for num in A:
num_hash[num] += 1
length += 1
answer = []
for num in A:
#print("num ::: " + str(num))
if answer_hash[num] != -1:
answer.append(answer_hash[num])
continue
count = 0
for measure in range(1, math.floor(num ** (1/2)) + 1):
#print("measure ::: " + str(measure))
if num % measure != 0:
continue
count += num_hash[measure]
if measure * measure != num:
count += num_hash[num // measure]
#print("num // measure ::: " + str(num // measure))
#print("count ::: " + str(count))
answer_hash[num] = length - count
answer.append(length - count)
#print(answer)
return answer
Analysis
Code: 09:52:30 UTC,
py,
verify,
result: Passed
import collections
import math
def solution(A):
num_hash = collections.defaultdict(int)
answer_hash = collections.defaultdict(lambda : -1)
length = 0
for num in A:
num_hash[num] += 1
length += 1
answer = []
for num in A:
#print("num ::: " + str(num))
if answer_hash[num] != -1:
answer.append(answer_hash[num])
continue
count = 0
for measure in range(1, math.floor(num ** (1/2)) + 1):
#print("measure ::: " + str(measure))
if num % measure != 0:
continue
count += num_hash[measure]
if measure * measure != num:
count += num_hash[num // measure]
#print("num // measure ::: " + str(num // measure))
#print("count ::: " + str(count))
answer_hash[num] = length - count
answer.append(length - count)
#print(answer)
return answer
Analysis
Code: 09:52:33 UTC,
py,
final,
score:
100
import collections
import math
def solution(A):
num_hash = collections.defaultdict(int)
answer_hash = collections.defaultdict(lambda : -1)
length = 0
for num in A:
num_hash[num] += 1
length += 1
answer = []
for num in A:
#print("num ::: " + str(num))
if answer_hash[num] != -1:
answer.append(answer_hash[num])
continue
count = 0
for measure in range(1, math.floor(num ** (1/2)) + 1):
#print("measure ::: " + str(measure))
if num % measure != 0:
continue
count += num_hash[measure]
if measure * measure != num:
count += num_hash[num // measure]
#print("num // measure ::: " + str(num // measure))
#print("count ::: " + str(count))
answer_hash[num] = length - count
answer.append(length - count)
#print(answer)
return answer
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N * log(N))
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
expand all
Performance tests
1.
0.072 s
OK
2.
0.052 s
OK
1.
0.228 s
OK
2.
0.076 s
OK
1.
0.368 s
OK
2.
0.104 s
OK
1.
0.148 s
OK
2.
0.100 s
OK
3.
0.120 s
OK