Test results - Codility

Tasks Details

medium

1. CountNonDivisible

Calculate the number of elements of an array that are not divisors of each element.

100%

Task description

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] = 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[4] = 6, there aren't any non-divisors.

Assume that the following declarations are given:

struct Results { int * C; int L; // Length of the array };

Write a function:

struct Results solution(int A[], int N);

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 a structure Results.

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.

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].

Solution

Programming language used C

Time spent on task 10 minutes

Notes

not defined yet

Task timeline

‌

Code: 13:20:42 UTC, c, verify, result: Passed

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#define MAX_N (50000)

int lp[2*MAX_N+1];
int fq[2*MAX_N+1];
int ds[2*MAX_N+1];
int pf[MAX_N+1];
int es[MAX_N+1];
int bs[MAX_N+1];
int rs[MAX_N+1];

int max(int x, int y) { return x > y ? x : y; }

struct Results solution(int * xs, int n) {
    struct Results result;
    int i,j,e,c,k,cnt,x,l,mx,acc;

    /* Build frequency table */
    for ( i=mx=0; i < n; ++i ) {
        fq[xs[i]] += 1;
        mx = max(mx, xs[i]);
    }
    /* Build least prime factor sieve */
    for ( i=2; i*i <= mx; ++i )
        if ( !lp[i] )
            for ( j=i*i; j <= mx; j+=i )
                if ( !lp[j] )
                    lp[j] = i;
    for ( c=0; c < n; ++c ) {
        /* Calculate prime factorization of xs[c] */
        for ( i=xs[c],cnt=0; lp[i]; i/= lp[i] )
            pf[cnt++] = lp[i];
        pf[cnt++] = i;
        /* Convert factorization into p1^n1, p2^n2,.. form */
        for ( i=1,j=0,bs[j]=pf[0],e=1; i < cnt; ++i )
            if ( pf[i] == bs[j] ) { e += 1; }
            else { es[j] = e; e=1; bs[++j] = pf[i]; }
        es[j++] = e;
        if ( xs[c] == 1) es[0] = 0;
        /* Calculate divisors given prime factors */
        cnt=1; ds[0] = 1;
        for ( i=0; i < j; ++i ) {
            x = cnt;
            for ( k=0; k < es[i]; ++k )
                for ( l=0; l < x; ++l )
                    ds[cnt++] = bs[i] * ds[l + k*x];
        }
        for ( i=0,acc=n; i < cnt; ++i )
            acc -= fq[ds[i]];
        rs[c] = acc;
    }

    result.C = rs;
    result.L = n;
    return result;
}

Code: 13:20:46 UTC, c, verify, result: Passed

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#define MAX_N (50000)

int lp[2*MAX_N+1];
int fq[2*MAX_N+1];
int ds[2*MAX_N+1];
int pf[MAX_N+1];
int es[MAX_N+1];
int bs[MAX_N+1];
int rs[MAX_N+1];

int max(int x, int y) { return x > y ? x : y; }

struct Results solution(int * xs, int n) {
    struct Results result;
    int i,j,e,c,k,cnt,x,l,mx,acc;

    /* Build frequency table */
    for ( i=mx=0; i < n; ++i ) {
        fq[xs[i]] += 1;
        mx = max(mx, xs[i]);
    }
    /* Build least prime factor sieve */
    for ( i=2; i*i <= mx; ++i )
        if ( !lp[i] )
            for ( j=i*i; j <= mx; j+=i )
                if ( !lp[j] )
                    lp[j] = i;
    for ( c=0; c < n; ++c ) {
        /* Calculate prime factorization of xs[c] */
        for ( i=xs[c],cnt=0; lp[i]; i/= lp[i] )
            pf[cnt++] = lp[i];
        pf[cnt++] = i;
        /* Convert factorization into p1^n1, p2^n2,.. form */
        for ( i=1,j=0,bs[j]=pf[0],e=1; i < cnt; ++i )
            if ( pf[i] == bs[j] ) { e += 1; }
            else { es[j] = e; e=1; bs[++j] = pf[i]; }
        es[j++] = e;
        if ( xs[c] == 1) es[0] = 0;
        /* Calculate divisors given prime factors */
        cnt=1; ds[0] = 1;
        for ( i=0; i < j; ++i ) {
            x = cnt;
            for ( k=0; k < es[i]; ++k )
                for ( l=0; l < x; ++l )
                    ds[cnt++] = bs[i] * ds[l + k*x];
        }
        for ( i=0,acc=n; i < cnt; ++i )
            acc -= fq[ds[i]];
        rs[c] = acc;
    }

    result.C = rs;
    result.L = n;
    return result;
}

Code: 13:20:49 UTC, c, final, score: 100

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#define MAX_N (50000)

int lp[2*MAX_N+1];
int fq[2*MAX_N+1];
int ds[2*MAX_N+1];
int pf[MAX_N+1];
int es[MAX_N+1];
int bs[MAX_N+1];
int rs[MAX_N+1];

int max(int x, int y) { return x > y ? x : y; }

struct Results solution(int * xs, int n) {
    struct Results result;
    int i,j,e,c,k,cnt,x,l,mx,acc;

    /* Build frequency table */
    for ( i=mx=0; i < n; ++i ) {
        fq[xs[i]] += 1;
        mx = max(mx, xs[i]);
    }
    /* Build least prime factor sieve */
    for ( i=2; i*i <= mx; ++i )
        if ( !lp[i] )
            for ( j=i*i; j <= mx; j+=i )
                if ( !lp[j] )
                    lp[j] = i;
    for ( c=0; c < n; ++c ) {
        /* Calculate prime factorization of xs[c] */
        for ( i=xs[c],cnt=0; lp[i]; i/= lp[i] )
            pf[cnt++] = lp[i];
        pf[cnt++] = i;
        /* Convert factorization into p1^n1, p2^n2,.. form */
        for ( i=1,j=0,bs[j]=pf[0],e=1; i < cnt; ++i )
            if ( pf[i] == bs[j] ) { e += 1; }
            else { es[j] = e; e=1; bs[++j] = pf[i]; }
        es[j++] = e;
        if ( xs[c] == 1) es[0] = 0;
        /* Calculate divisors given prime factors */
        cnt=1; ds[0] = 1;
        for ( i=0; i < j; ++i ) {
            x = cnt;
            for ( k=0; k < es[i]; ++k )
                for ( l=0; l < x; ++l )
                    ds[cnt++] = bs[i] * ds[l + k*x];
        }
        for ( i=0,acc=n; i < cnt; ++i )
            acc -= fq[ds[i]];
        rs[c] = acc;
    }

    result.C = rs;
    result.L = n;
    return result;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N * log(N))

▶

example
example test

✔

▶

extreme_simple
extreme simple

✔

▶

double
two elements

✔

▶

simple
simple tests

✔

▶

primes
prime numbers

✔

▶

small_random
small, random numbers, length = 100

✔

▶

medium_random
medium, random numbers length = 5,000

✔

▶

large_range
1, 2, ..., N, length = ~20,000

✔

▶

large_random
large, random numbers, length = ~30,000

✔

▶

large_extreme
large, all the same values, length = 50,000

✔