Geek Answers Handbook

CountNonDivisible - The task of learning codiality

Now I translate to agility. I can solve some problems on my own, but problems arise with some tasks. The complexity of this task <**>. It is average, but I stopped.

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 in the array that are not divisors of A [i]. We say that these elements are not divisors. For example, consider an integer N = 5 and an array A such that:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6

For the following items:

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); }

, A , N , , . :

  • ( ),
  • ( C++),
  • ( ),
  • ( ).

, :

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6

[2, 4, 3, 2, 0], . , :

  • N [1,50 000];
  • A [1..2 * N].

:

  • O (N * log (N));
  • O (N), ( , ).

.

. O (n ^ 2). , ? - . . : http://codility.com/demo/train/ 9, .

!

+8
18

: (EDITED, . )

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;
    }
}

, , 2 * arrayLength. , ,

  • ( Erathostenes)

, . , , . , .

( , logN), O (N * logN). , O (N), N . , , , , , O (N * logN).

EDIT: , A.length * 2-1, . , , . ,

got      [8, 8, 9, 10, 6, 8, .. 
expected [8, 8, 9, 10, 6, 8, ..

. , "", . , , , - ; -P O (N), ...

+4

, C++, 100 . , .

https://codility.com/demo/results/demoQFK5R5-YGD/

  1. .

  2. i 1 sqrt(i), , .

  3. , .

    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;
}
+8

100 . 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;
}

.

+6

100- Python-. , .

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
+3

, 100%:

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;
   }

https://codility.com/demo/results/trainingZ2VRTK-5Y9/

+2

- o (nlogn) o (n)

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;
    }
}
+2

, "2" [2,4,3,2,0], .

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
0

-! [0] 2 , [3] 2 .

0

100% 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;
}
0

100% 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;
}
0

javascript. , , , O (n log n). : 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 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;
}
0

//++ 100%, . // , .

void make_factorization_array (int N, std::vector & sieve) {

for(int i = 2;i*i <= N;i++)
{
    if(sieve[i] == 0)
    {
        int k = i*i;
        for(int j = k;j <= N;j += i)
        {
            auto& e = sieve[j];
            if(e == 0)
                e = i;   
        }

    }

}

}

int count_divisors (std::vector & divisors, std::vector > & primes, int prime_index, int initial) {

auto& p = primes[prime_index];

int c = 0;

int v = initial;

int max = p.second;

if(p.first == 1)
    max = 0;

for(int i = 0;i <= max;i++)
{                   

    if(prime_index != primes.size() - 1)
        c += count_divisors(divisors, primes, prime_index + 1, v);
    else
        c += divisors[v];

    v = v * p.first;

}

return c;

}

( & A) {   // ++ 11 (g++ 4.8.2)

int me = *std::max_element(A.begin(), A.end());

std::vector<int> factorization_array;
std::vector<int> sieve(me + 1, 0);
make_factorization_array(me, sieve);     

std::vector<int> divisors(me + 1, 0);        
for(auto i = A.begin();i != A.end();i++)
    divisors[*i]++;   

vector<int> r;
r.reserve(A.size());

for(auto i = A.begin();i != A.end();i++){


    std::vector<std::pair<int, int> > primes;
    primes.reserve(*i);

    int k = *i;

    int last_prime = 0;
    int power = 0;

    while(sieve[k] > 0)
    {
        if(last_prime != sieve[k])
        {
            if(last_prime != 0)
                primes.push_back(std::make_pair(last_prime, power));
            power = 1;
            last_prime = sieve[k];
        } else
        {
            power++;   
        }                
        k = k / sieve[k];                        
    } 

    if(last_prime == k)
        primes.push_back(std::make_pair(last_prime, power + 1));
    else
    {
        if(last_prime != 0)
            primes.push_back(std::make_pair(last_prime, power));
        primes.push_back(std::make_pair(k, 1));
    }                                

    int c = count_divisors(divisors, primes, 0, 1);            

    r.push_back(A.size() - c);
}
return r;

}

0

100% , 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
}

@Soley.

0

Based on jaho's answer, I added a cache to avoid the same calculations.

Here is the result of codility ,

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 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;
}
0
source 
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;
  }
0
source

Here's a 100% python using the Sieve of Eratosthenes principle to avoid counting divisors (or multiples) more than once to the maximum 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
0
source

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
0
source 
/**
 * 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]);
        }
    }
}
-1
source

More articles:


All Articles