'CountNonDivisible - Codility training task
I'm traning on codility now. Some tasks I can solve by myself, but with some tasks have problems. Difficulty of this task is <**>. It's medium, but I stalled.
Problem:
You are given a non-empty zero-indexed 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] = 6
For 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[6] = 6, there aren't any non-divisors.
Write a function:
class Solution { public int[] solution(int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers, returns a sequence of integers representing the numbers of non-divisors. The sequence should be returned as:
- a structure Results (in C),
- or a vector of integers (in C++),
- or a record Results (in Pascal),
- or an array of integers (in any other programming language).
For example, given:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6
the function should return [2, 4, 3, 2, 0], as explained above. Assume that:
- N is an integer within the range [1..50,000];
- each element of array A is an integer within the range [1..2 * N].
Complexity:
- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
I have written some solutions. But my solutions bulky and still have O(n^2) complexity. Can you help me with some ideas or algorithms how to do it optimally? It's not an interview task or something else. I'm just training and try to solve all tasks. You can find this task here: http://codility.com/demo/train/ Lesson 9, first task in lesson.
Thank you!
Solution 1:[1]
A solution attempt: (EDITED, see below)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// Solution for Lesson 9, "CountNonDivisible"
// of http://codility.com/demo/train/
public class Solution
{
public static void main(String[] args)
{
int A[] = new int[5];
A[0] = 3;
A[1] = 1;
A[2] = 2;
A[3] = 3;
A[4] = 6;
Solution s = new Solution();
int B[] = s.solution(A);
System.out.println("Input : "+Arrays.toString(A));
System.out.println("Result : "+Arrays.toString(B));
}
public int[] solution(int[] A)
{
Set<Integer> setA = asSet(A);
List<Set<Integer>> divisors = computeDivisors(A.length * 2);
int occurrences[] = computeOccurrences(A);
int nonDivisors[] = new int[A.length];
for (int i=0; i<A.length; i++)
{
int value = A[i];
Set<Integer> d = divisors.get(value);
int totalOccurances = 0;
for (Integer divisor : d)
{
if (setA.contains(divisor))
{
totalOccurances += occurrences[divisor];
}
}
nonDivisors[i] = A.length-totalOccurances;
}
return nonDivisors;
}
/**
* Returns a set containing all elements of the given array
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The set
*/
private static Set<Integer> asSet(int A[])
{
Set<Integer> result = new HashSet<Integer>();
for (int value : A)
{
result.add(value);
}
return result;
}
/**
* Computes a list that contains for each i in [0...maxValue+1] a set
* with all divisors of i. This is basically an "Eratosthenes Sieve".
* But in addition to setting the entries of a list to 'false'
* (indicating that the respective numbers are non-prime), this
* methods inserts the divisors into the corresponding set.
*
* Space: O(N) (?)
* Time: O(N*logN) (?)
*
* @param maxValue The maximum value
* @return The list
*/
private static List<Set<Integer>> computeDivisors(int maxValue)
{
List<Boolean> prime = new ArrayList<Boolean>();
prime.addAll(Collections.nCopies(maxValue+1, Boolean.TRUE));
List<Set<Integer>> divisors = new ArrayList<Set<Integer>>();
for (int i = 0; i < maxValue + 1; i++)
{
Set<Integer> d = new HashSet<Integer>();
d.add(1);
d.add(i);
divisors.add(d);
}
for (int i = 2; i <= maxValue; i++)
{
int next = i + i;
while (next <= maxValue)
{
divisors.get(next).addAll(divisors.get(i));
prime.set(next, Boolean.FALSE);
next += i;
}
}
return divisors;
}
/**
* Computes an array of length 2*A.length+1, where each entry i contains
* the number of occurrences of value i in array A
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The occurrences array
*/
private static int[] computeOccurrences(int A[])
{
int occurances[] = new int[A.length * 2 + 1];
for (int i=0; i<A.length; i++)
{
int value = A[i];
occurances[value]++;
}
return occurances;
}
}
The maximum value for the numbers that occur in the array was defined to be 2*arrayLength. For each number that MAY occur in the array, it computes
- The set of divisors of this number (using the Erathostenes Sieve)
- How often the number actually occurs in the array
Given this information, one can walk through the array. For each value that is found in the array, one can look up the set of divisors, and compute the total number occurences of all the divisors. The result is then simply the array length, minus this total number of occurances of divisors.
Since it uses only the Sieve of Erathostenes for the computation (and only walks through the set of divisors for each number, which should be logN as well), it should have a worst-case time complexity of O(N*logN). But I'm not entirely sure whether the storage complexity really can be considered to be strictly O(N), because for each of the N numbers, it has to store the set of divisors. Maybe this can somehow be avoided, by combining some of the methods, but in any case, the storage is at least in O(N*logN) as well.
EDIT: The exceptions came from the array for the occurrences storing only values up to A.length*2-1, this was fixed now. Additionally, the set of divisors was not computed properly, this should also be fixed now. Apart from that, analysis results like
got [8, 8, 9, 10, 6, 8, ..
expected [8, 8, 9, 10, 6, 8, ..
are not really helpful. Maybe this is part of the "game", but I'm not playing this game right now. The basic idea should be clear, and I assume that it's now working properly until someone shows be a counterexample ;-P It still does not reach the O(N) storage complexity, but I haven't thought about a possible way to achieve this thoroughly...
Solution 2:[2]
I thought I'll share my solution in C++ which gets 100 score. I think it's pretty straightforward.
https://codility.com/demo/results/demoQFK5R5-YGD/
First it counts the occurrences of each number in the array.
Then for each array element
iit finds the number of its divisors in a range from 1 tosqrt(i), including the divisors which are the result of the division.Finally it subtracts a total number of divisors for given element from a total number of elements in the array.
vector<int> solution(vector<int> &A) { int N = A.size(); vector<int> counts (*std::max_element(A.begin(), A.end()) + 1,0); // Calculate occurences of each number in the array for (int i = 0; i < N; ++i) { counts[A[i]] += 1; } std::vector<int> answer(N,0); // For each element of the array for (int i = 0; i < N; ++i) { // Calulate how many of its divisors are in the array int divisors = 0; for (int j = 1; j * j <= A[i]; ++j) { if (A[i] % j == 0) { divisors += counts[j]; if (A[i] / j != j) { divisors += counts[A[i] / j]; } } } // Subtract the number of divisors from the number of elements in the array answer[i] = N - divisors; } return answer; }
Solution 3:[3]
This solution gives 100 score. https://codility.com/demo/results/demo63KVRG-Q63/
public int[] solution(int[] A) {
int[][] D = new int[A.length*2 + 1][2];
for (int i = 0; i < A.length; i++) {
D[A[i]][0]++;
D[A[i]][1] = -1;
}
for (int i = 0; i < A.length; i++) {
if (D[A[i]][1] == -1) {
D[A[i]][1] = 0;
for (int j = 1; j <= Math.sqrt(A[i]) ; j++) {
if (A[i] % j == 0 && A[i] / j != j) {
D[A[i]][1] += D[j][0];
D[A[i]][1] += D[A[i]/j][0];
} else if (A[i] % j == 0 && A[i] / j == j) {
D[A[i]][1] += D[j][0];
}
}
}
}
for (int i = 0; i < A.length; i++) {
A[i] = A.length - D[A[i]][1];
}
return A;
}
Thank you all for your help.
Solution 4:[4]
Here is my 100 score Python solution. Hope it is helpful to others.
def solution(A):
''' Solution for the CountNonDivisible by codility
Author: Sheng Yu - codesays.com
'''
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
# useless 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
Solution 5:[5]
Here we go with the solution I got 100% on:
boolean[] result_;
public int[] solution(int[] A) {
int a[][] = new int[2*A.length + 1][2];
result_ = new boolean[2*A.length + 1];
for(int i : A) {
++a[i][0];
}
a[1][1] = A.length - a[1][0];
result_[1] = true;
for(int i : A) {
multCount(a,A,i);
}
int[] result = new int[A.length];
for(int i=0;i<result.length; i++) {
result[i] = a[A[i]][1];
}
return result;
}
private void multCount( int[][] a, int[] A, int item) {
if( result_[item] )
return;
int sub=(int)Math.sqrt(item);
a[item][1] = A.length;
if(item % sub == 0&& sub >1){
a[item][1] -= a[sub][0];
int rest = item/sub;
if(rest != sub) {
a[item][1] -= a[rest][0];
}
}
a[item][1] -= a[item][0];
a[item][1] -= a[1][0];
for(int i=2; i<sub; i++) {
if(item % i == 0) {
a[item][1] -= a[i][0];
int rest = item/i;
a[item][1] -= a[rest][0];
}
}
result_[item] = true;
}
Solution 6:[6]
I used a hashmap and it satisfies o(nlogn) and o(n) time and space complexities
import java.util.*;
class Solution {
public int[] solution(int[] A) {
int N = A.length;
HashMap<Integer, Integer> count = new HashMap<>();
for (int i : A) {
Integer key = count.get(i);
if (key != null) {
count.put(i, key + 1);
} else {
count.put(i, 1);
}
}
HashMap<Integer, Integer> divs = new HashMap<>();
for (Integer n : count.keySet()) {
int sum = 0;
int j = 1;
while (j * j <= n) {
if (n % j == 0) {
if (count.containsKey(j)) {
sum += count.get(j);
}
//find n = j*k cases to add both to the dividors
int k = n / j;
if (k != j) {
if (count.containsKey(k)) {
sum += count.get(k);
}
}
}
j++;
}
divs.put(n, N - sum);
}
for (int i = 0; i < A.length; i++) {
A[i] = divs.get(A[i]);
}
return A;
}
}
Solution 7:[7]
100% Scored Solution, ES6:
function solution(A) {
let count = {}
// counting number frequency
A.map(a => {
//console.log(count[a])
if (count[a] > 0) {
count[a] = count[a] + 1
} else {
count[a] = 1
}
})
// console.log(count)
let divs = {}
Object.keys(count).map(key => {
let sum = 0
let j = 1
while (j * j <= key) {
if (key % j == 0) {
if (count[j] > 0) {
sum += count[j]
}
// adding another dividor
let k = key / j
// scenario: 9 = 81 / 9. Escaping same number
if (k != j) {
if (count[k] > 0) {
sum += count[k]
}
}
// another possible solution: sum = sum * 2
// if key is square number: sum -= 1
}
j++
}
divs[key] = A.length - sum
})
// console.log(divs)
let answer = []
A.map(a => {
answer.push(divs[a])
})
// console.log(answer)
return answer
}
Inspired by @Soley's solution.
Solution 8:[8]
Ruby solution, 100%
def solution(a)
elements = a.inject(Hash.new(0)) {|acc, el| acc[el] +=1;acc }
n = elements.keys.sort
div = n.each.inject(Hash.new(0)) do |acc, el|
k=el
while k < n[-1]
k+=el
acc[k] += elements[el]
end
acc
end
a.map {|x| a.size - elements[x] - div[x] }
end
Solution 9:[9]
This 100/100 code solution in C#. As C# and Java pretty similar might be helpful.
public class NonDivisiblesCounter
{
/// <summary>
/// 1. Count the ocurrences of each element
/// 2. Count all divisors for each element and subtract by the Length of array A to get nonDivisors
/// 3. Add it to a cache since the elements can repeat and you do not need to calculate again.
/// </summary>
/// <param name="A"></param>
/// <returns></returns>
public int[] Count(int[] A)
{
int n = A.Length;
var ocurrencesOfEach = CountOcurrencesOfEach(A);
var nonDivisorsOfEach = new int[n];
var nonDivisorsCache = new Dictionary<int, int>();
for (int i = 0; i < n; i++)
{
int element = A[i];
if (nonDivisorsCache.ContainsKey(element))
{
nonDivisorsOfEach[i] = nonDivisorsCache[element];
}
else
{
int nonDivisorCounter = n - CountDivisorsPerOcurrence(element, ocurrencesOfEach);
nonDivisorsOfEach[i] = nonDivisorCounter;
nonDivisorsCache[element] = nonDivisorCounter;
}
}
return nonDivisorsOfEach;
}
private int CountDivisorsPerOcurrence(int element, Dictionary<int, int> ocurrencesOfEach)
{
int square = (int)Math.Sqrt(element);
int divisorCounter = 0;
if (square * square == element && ocurrencesOfEach.ContainsKey(square))
{
divisorCounter += ocurrencesOfEach[square];
}
for (int divisor = 1; element / divisor > square; divisor++)
{
if (element % divisor == 0)
{
if (ocurrencesOfEach.ContainsKey(divisor))
{
divisorCounter += ocurrencesOfEach[divisor];
}
if (ocurrencesOfEach.ContainsKey(element / divisor))
{
divisorCounter += ocurrencesOfEach[element / divisor];
}
}
}
return divisorCounter;
}
private Dictionary<int, int> CountOcurrencesOfEach(int[] elements)
{
var result = new Dictionary<int, int>();
for (int i = 0; i < elements.Length; i++)
{
int element = elements[i];
if (result.ContainsKey(element))
{
result[element]++;
}
else
{
result.Add(element, 1);
}
}
return result;
}
}
Solution 10:[10]
Because that return numbers represents the quantity of non-divisors! For index [0] there are 2 non-divisers and for index [3] there are 2 non-divisers also.
Solution 11:[11]
This worked for me with 100% score on C
struct Results solution(int A[], int N) {
struct Results result;
// write your code in C99
int *numbers = (int *)calloc(2*N + 1, sizeof(int));
for (int i = 0; i < N; i++) {
++numbers[A[i]];
}
int *numbers2 = (int *)calloc(2*N + 1, sizeof(int));
for (int i = 0; 2*i < 2*N + 1; i++) {
if (numbers[i] != 0) {
for (int j = 2*i; j < 2*N + 1; j+=i) {
numbers2[j] += numbers[i];
}
}
}
int * Carr = (int *)calloc(N, sizeof(int));
for (int i = 0; i < N; i++) {
Carr[i] = N - numbers[A[i]] - numbers2[A[i]];
}
result.C = Carr;
result.L = N;
free(numbers);
free(numbers2);
return result;
}
Solution 12:[12]
100% for Javascript. https://codility.com/demo/results/demoKRRRPF-8JW/
function solution(A) {
var N = A.length;
if (N < 1 || N > 50000) throw 'Error: Bad input';
var uniqueDict = {};
var keys = [];
for (var i = 0; i < N; ++i) {
var num = A[i]
var uniqueCount = uniqueDict[num];
if (uniqueCount > 0) {
uniqueDict[num] = uniqueCount + 1;
} else {
uniqueDict[num] = 1;
keys.push(num);
}
}
keys.sort(function(a,b){
return a-b;
});
for (i = keys.length-1; i >= 0; --i) {
num = keys[i];
var divisorCount = divisors(num, uniqueDict);
var nonDivisorCount = N - divisorCount;
uniqueDict[num] = nonDivisorCount;
}
for (i = 0; i < N; ++i) {
num = A[i];
A[i] = uniqueDict[num];
}
return A;
}
function divisors(num, uniqueDict) {
var count = 0;
var x = 1;
while (x * x <= num) {
if (parseInt(num/x) === num/x) { // is divisor
if (uniqueDict[num/x] > 0) {
count += uniqueDict[num/x];
}
if (num/x !== x && uniqueDict[x] > 0) {
count += uniqueDict[x];
}
}
x++;
}
return count;
}
Solution 13:[13]
Here is my solution in javascript. I think it is a little bit easier than previous ones and it works on O(n log n). You can check other solutions here: https://marioqs.wordpress.com
function solution(A) {
var N = A.length;
var count = [];
var i;
for (i = 0; i < 2*N+1; ++i){
count.push(0);
}
for (i = 0; i < N; ++i){
++count[A[i]];
}
var divisors = [];
for (i = 0; i < 2*N+1; ++i){
divisors.push(0);
} //the actual code starts here, before it's just initialisation of variables.
i = 1;
var k;
while (i <= 2*N){
k = i;
while (k <= 2*N){
divisors[k] += count[i];
k += i;
}
++i;
}
var result = [];
for (i = 0; i < N; ++i){
result.push(0);
}
for (i = 0; i < N; ++i){
result[i] = N - divisors[A[i]];
}
return result;
}
Solution 14:[14]
Based on jaho's answer, I added the cache to avoid the same computation.
Here is the codility result,
and below is my C code.
#include <math.h>
struct Results solution(int A[], int N) {
int maxA = 0, i, j, sqrtA;
int *counts, *cache;
struct Results result;
result.C = (int *) malloc(N*sizeof(int));
result.L = N;
// Grep the maximum.
for (i = 0; i < N; ++i) {
if (A[i] > maxA)
maxA = A[i];
}
++maxA;
// Initialize some arrays.
counts = (int *) malloc(maxA*sizeof(int));
cache = (int *) malloc(maxA*sizeof(int));
for (i = 0; i < maxA; ++i) {
counts[i] = 0;
cache[i] = -1;
}
// Count A.
for (i = 0; i < N; ++i) {
counts[A[i]] += 1;
}
// Main computation begins.
for (i = 0; i < N; ++i) {
// If the answer is already computed, use it.
if (cache[A[i]] >= 0) {
result.C[i] = cache[A[i]];
continue;
}
// There's no existing answer, compute it.
cache[A[i]] = N;
sqrtA = (int) sqrt(A[i]);
for (j = 1; j <= sqrtA; ++j) {
if (A[i]%j == 0) {
cache[A[i]] -= counts[j];
if (j*j != A[i]) {
cache[A[i]] -= counts[A[i]/j];
}
}
}
result.C[i] = cache[A[i]];
}
// Since Codility prohibits the system calls,
// below free commands are commented.
// free(counts);
// free(cache);
return result;
}
Solution 15:[15]
import static java.lang.Integer.max;
import java.util.Arrays;
public int[] solution(int[] A) {
final int N = A.length;
final int MAX_VALUE_TBL = 2*50000;
int[] r = new int[N]; // result table
int[] AS_AV = new int[MAX_VALUE_TBL + 1]; // number of cell with values
int[] AS_AR = new int[MAX_VALUE_TBL + 1]; // results yet counted for values
boolean[] b = new boolean[MAX_VALUE_TBL + 1]; // if value has been counted
if (N == 1) return r;
for (int i = 0; i < N; i++) {
int v = A[i];
AS_AV[v]++;
}
for (int i = 0; i < N; i++) {
int cu_val = A[i];
if (!b[cu_val]) {
int am_div = getAmDivisors(cu_val, AS_AV);
r[i] = N - am_div;
b[cu_val] = true;
AS_AR[cu_val] = r[i];
} else {
r[i] = AS_AR[cu_val];
}
}
return r;
}
private int getAmDivisors(int cu_val, int[] AS_AV) {
int r = 0;
int sqr = (int) Math.sqrt(cu_val);
for (int divisor = sqr; divisor > 0; divisor--) {
if (cu_val % divisor == 0) {
r += AS_AV[divisor];
if (divisor * divisor != cu_val) {
r += AS_AV[cu_val / divisor];
}
}
}
return r;
}
Solution 16:[16]
Here 100% python using Sieve of Eratosthenes principal to avoid counting divisors (or multiple) more than one time until the maximal value of the array:
def solution(A):
N=len(A)
num_non_divisors=[0]*N
if N<2:
return num_non_divisors
MaxVal=max(A)
#Trivial cases
if MaxVal < 2:
return num_non_divisors
MinVal=min(A)
if MinVal==MaxVal:
return num_non_divisors
Occur = [0] * (MaxVal + 1)
#Occurences of e in A
for e in A:
Occur[e]+=1
#Divisors of any element lower than MaxVal
Divisors = [Occur[1]] * (MaxVal + 1)
#DejaVu to avoid counting them more than once
DejaVu = [0] * (MaxVal + 1)
for e in A:
if e!=1 and DejaVu[e]==0:
Divisors[e]+=Occur[e]
DejaVu[e]+=1
i = 2
while (i * i <= MaxVal):
#We start at i x i to avoid counting 2 times multiples of the form k x i, where k<i.
k = i * i
while (k <= MaxVal):
Divisors[k] += Occur[i]
if i * i < k: #equivalent k/i != i
#Symmetric divisor
Divisors[k] += Occur[int(k/i)];
k += i
i += 1
#Re-initialize DejaVu
DejaVu = [0] * (MaxVal + 1)
for i in range(0,len(A)):
if not DejaVu[A[i]]:
DejaVu[A[i]]=N-Divisors[A[i]]
num_non_divisors[i]=DejaVu[A[i]]
return num_non_divisors
Solution 17:[17]
Here is my java solution, 100%.
No modulo, no division. Just 'count sort' and sieve.
public int[] solution(int[] A) {
//find max number. To be used for 'count sort' array size.
int max = A[0];
for (int i = 1 ; i < A.length ; i++) {
max = Math.max(max, A[i]);
}
//count sort
int [] count = new int [max+1];
for (int i = 0 ; i < A.length ; i++) {
count[A[i]]++;
}
int [] nonDiv = new int [max+1];
//initially count all elements as non divisible (minus 'number of occurrences' of the the given number)
for (int i = 1 ; i < nonDiv.length; i++) {
if (count[i] != 0) {//skip numbers which don't exists in table A
nonDiv[i] = A.length - count[i];
}
}
//sieve
for (int i = 1 ; i < nonDiv.length; i++) {
if (count[i] != 0) {//skip numbers which don't exists in table A
int s = i*2;
while (s<nonDiv.length) {
if (nonDiv[s] != 0) {
//Sieve. Most important part. Decrease number of non-divisible by the number of occurrences of number 'i'.
nonDiv[s] -= count[i];
}
s+=i;
}
}
}
//produce the output
int []res = new int [A.length];
for (int i = 0 ; i < A.length ; i++) {
res[i] = nonDiv[A[i]];
}
return res;
}
Solution 18:[18]
Golang solution got 100%, the only difference is that we have to use hashmap to cache the divisors, or the performance testing will partly fail.
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) []int {
tdMapping := make(map[int]int)
MaxValue := 2 * len(A)
occurs := make([]int, MaxValue+1)
for _, v := range A {
occurs[v]++
}
r := make([]int, len(A))
for i := 0; i < len(A); i++ {
totalDivisors := 0
if _, ok := tdMapping[A[i]]; ok {
totalDivisors = tdMapping[A[i]]
} else {
for j := 1; j*j <= A[i]; j++ {
if j*j == A[i] {
totalDivisors += occurs[j]
} else {
if A[i]%j == 0 {
totalDivisors += occurs[j] + occurs[A[i]/j]
}
}
}
tdMapping[A[i]] = totalDivisors
}
r[i] = len(A) - totalDivisors
}
return r
}
Solution 19:[19]
JavaScript solution with 100% score. Codility detected the complexity to be O(nlogn), but it's actually O(n * sqrt(n))
function solution(A) {
const createCounts = A => {
const counts = Array(A.length * 2 + 1).fill(0)
for (let i = 0; i < A.length; i++) {
counts[A[i]] += 1
}
return counts
}
const counts = createCounts(A)
const results = []
for (let i = 0; i < A.length; i++) {
let nonDivisiblesCount = A.length
let j = 1
while (j * j < A[i]) {
if (A[i] % j === 0) {
nonDivisiblesCount -= counts[j]
nonDivisiblesCount -= counts[A[i] / j]
}
j++
}
if (j * j === A[i]) {
nonDivisiblesCount -= counts[j]
}
results.push(nonDivisiblesCount)
}
return results
}
const A = [3, 1, 2, 3, 6]
console.log(A)
const s = solution(A)
console.log(s)
Solution 20:[20]
One of the most difficult to read solution written in GO lang, designed by Java developer (100% total score):
func Solution(A []int) []int {
aSize := len(A)
maxValue := A[0]
for idx := 0; idx < aSize; idx++ {
element := A[idx]
if maxValue < element {
maxValue = element
}
}
remainDividersCountList := make([]int, maxValue+1)
for idx := 0; idx < aSize; idx++ {
element := A[idx]
if remainDividersCountList[element] == 0 {
remainDividersCountList[element] = aSize - 1
} else {
remainDividersCountList[element] = remainDividersCountList[element] - 1
}
}
cachedResultMap := make([]int, maxValue+1)
alreadyCalculated := make([]int, maxValue+1)
alreadyCalculatedDuplicated := make([]int, maxValue+1)
caluclatedMap := make(map[int][]int)
for idx := 0; idx < aSize; idx++ {
element := A[idx]
if alreadyCalculated[element] == 0 {
for multiplier := 2; multiplier <= maxValue/element; multiplier++ {
multResult := element * multiplier
if multResult > maxValue {
break
} else {
cachedResult := cachedResultMap[multResult]
if cachedResult > 0 {
cachedResultMap[multResult] = cachedResult + 1
} else {
cachedResultMap[multResult] = 1
}
caluclatedMap[element] = append(caluclatedMap[element], multResult)
}
}
alreadyCalculated[element] = 1
} else if alreadyCalculatedDuplicated[element] == 0 {
multiplier := aSize - (remainDividersCountList[element] + 1)
list := caluclatedMap[element]
for repIdx := 0; repIdx < len(list); repIdx++ {
repElem := list[repIdx]
cachedResultMap[repElem] = cachedResultMap[repElem] + (1 * multiplier)
}
alreadyCalculatedDuplicated[element] = 1
}
}
result := make([]int, aSize)
for idx := 0; idx < aSize; idx++ {
element := A[idx]
result[idx] = remainDividersCountList[element] - cachedResultMap[element]
}
return result
}
Solution 21:[21]
Performance is not the best of this code but readability is pretty straightforward.
Map<Integer, Long> map = IntStream.range(0, A.length)
.collect(HashMap::new,
(acc, i) -> acc.compute(A[i], (k, v) -> v == null ? 1 : ++v),
HashMap::putAll);
int[] removed = new int[A.length];
for (int i = 0; i < A.length; i++) {
int N = A[i];
int max = N;
List<Integer> divisors = new ArrayList<>();
if (N == 1) {
divisors.add(1);
} else {
for (int div = 1; div < max; div++) {
if (N % div == 0) {
divisors.add(div);
if (div != N / div) {
divisors.add(N / div);
}
}
if (N / div < max) {
max = N / div;
}
}
}
removed[i] += map.entrySet().stream()
.filter(entry -> divisors.stream().noneMatch(div -> Objects.equals(entry.getKey(), div)))
.mapToLong(e -> e.getValue()).sum();
Solution 22:[22]
// write your code in Swift 4.2.1 (Linux)
public func solution(_ A : inout [Int]) -> [Int] {
let n = A.count
var counters = Array(repeating: 0, count: 2 * n + 1)
var divisors = Array(repeating: 0, count: 2 * n + 2)
var nonDivisors = Array(repeating: 0, count: n)
for i in A {
counters[i] += 1
}
for i in 1...2 * n {
if counters[i] > 0 {
var k = i
while k <= 2 * n {
if counters[k] > 0 {
divisors[k] += counters[i]
}
k += i
}
}
}
for i in 0..<n {
nonDivisors[i] = n - divisors[A[i]]
}
return nonDivisors
}
var array = [3, 1, 2, 3, 6]
var a = solution(&array)
Solution 23:[23]
A 100% python solution that is easy to follow - I think :-)
First you will need the divisor count.
def get_divisors(n):
froot = int(n**.5)
divs = set()
# reverse through possible divisors which are lower than root(n)
while froot > 0:
if not n%froot:
divs.add(froot)
divs.add(n//froot) # Catch the higher divisor on the other side of froot
froot-=1
return divs
Then you can count the frequency of each int first making it easier to calculate the non divisors. Put the non divisors in a dict and simply retrieve the answer in a list comprehension at the end.
def solution(A):
N = len(A)
int_count = {}
# O(N) scan to count number frequency
for i in range(N):
int_count[A[i]] = int_count.get(A[i], 0) + 1
# Create an array for every i non-divisor count
div_count = {}
for i, freq in int_count.items():
divs = get_divisors(i)
num_divs = 0
for d in divs:
num_divs += int_count.get(d, 0)
div_count[i] = N-num_divs # N - divisors = non-divisors :-)
return [div_count[A[i]] for i in range(N)]
It is nice to occasionally do a solution that takes advantage of python :-)
Solution 24:[24]
To understand why number "2" appears twice on following result [2,4,3,2,0] see code below:
A[0] = 3, the non-divisors are: 2, 6 >> Quantity: 2
A[1] = 1, the non-divisors are: 3, 2, 3, 6 >> Quantity: 4
A[2] = 2, the non-divisors are: 3, 3, 6, >> Quantity: 3
A[3] = 3, the non-divisors are: 2, 6 >> Quantity: 2
A[6] = 6, there aren't any non-divisors. >> Quantity: 0
Solution 25:[25]
O(n * logn) solution in C++ below.
Check the max element in A to spare space rather than using sizeA * 2
Build a hash of the number occurrences in A.
Add {1, num} as divisors to all numbers. Divisors are stored in an unordered_set for effective insertion and lookup. The elements will also be unique.
Add all other divisors to all numbers.
Go through each number in A. Check how many times the divisors occur in A.
The non-divisors will be the length of A minus the found divisors.
vector<int> solution(vector<int> &A)
{
const int sizeA = A.size();
const int max_elem = *max_element(A.cbegin(), A.cend());
vector<int> hash(max_elem, 0);
vector<unordered_set<int>> divisors_hash(max_elem, unordered_set<int>{});
for (const int e : A) {
++hash[e - 1];
divisors_hash[e - 1].insert({1, e});
}
for (int i = 2; i * i <= max_elem; ++i) {
for (int k = i; k <= max_elem; k += i) {
if (hash[k - 1]) divisors_hash[k - 1].insert({i, k / i});
}
}
vector<int> non_divisors(sizeA, 0);
for (int i = 0; i < sizeA; ++i) {
const int e = A[i];
int divisor_count = 0;
for (const int divisor : divisors_hash[e - 1]) {
divisor_count += hash[divisor - 1];
}
non_divisors[i] = sizeA - divisor_count;
}
return non_divisors;
}
Solution 26:[26]
public class Solution {
public int[] solution(int[] A) {
int N = A.length;
int maxItem = A[0];
for (int i = 0; i < N; i++) {
maxItem = Math.max(maxItem, A[i]);
}
int[] count = new int[maxItem + 1];
for (int i = 0; i < A.length; i++) {
count[A[i]]++;
}
int[] answer = new int[N];
for (int i = 0; i < N; i++) {
int divisorsCount = 0;
for (int j = 1; j * j <= A[i]; j++) {
if (A[i] % j == 0) {
divisorsCount += count[j];
if (A[i]/j != j) {
divisorsCount += count[A[i]/j];
}
}
}
answer[i] = N - divisorsCount;
}
return answer;
}
}
Solution 27:[27]
/**
* Count Non-divisible
*/
public class Solution {
public int[] solution(int[] A) {
int[] div = new int[A.length];
for (int e = 0; e < div.length; e++) {
div[e] = 0;
for (int i = 0; i < A.length; i++) {
int dividend = A[e];
if (dividend % A[i] != 0) {
div[e] += 1;
}
}
}
return div;
}
public static void main(String args[]) {
int[] A = new int[]{3, 1, 2, 3, 6};
Solution s = new Solution();
int[] B = s.solution(A);
for (int i = 0; i < B.length; i++) {
System.out.println(B[i]);
}
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow