Test results - Codility

Tasks Details

medium

1. CountNonDivisible

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

100%

Not assessed

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.

Write a function:

vector<int> solution(vector<int> &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 a vector of integers.

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 2 minutes

Notes

not defined yet

Task timeline

Code: 18:37:02 UTC, cpp, 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

// you can also use includes, for example:
// #include <algorithm>

#include <algorithm>

vector<int> solution(vector<int> &A) {
    
    int N = A.size();
    vector<int> counts (*std::max_element(A.begin(), A.end()),0);
    
    // Calculate occurences of each number in the array
    for (int i = 0; i < N; ++i)
    {
        counts[A[i]] += 1;
    }

    // Assume each number has 0 non dividers
    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;
}

Analysis

▶

example
example test

✔

Code: 18:37:33 UTC, cpp, 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

// you can also use includes, for example:
// #include <algorithm>

#include <algorithm>

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

    // Assume each number has 0 non dividers
    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;
}

Analysis

▶

example
example test

✔

Code: 18:38:02 UTC, cpp, 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

// you can also use includes, for example:
// #include <algorithm>

#include <algorithm>

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

    // Assume each number has 0 non dividers
    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;
}

Analysis

▶

example
example test

✔

Code: 18:38:07 UTC, cpp, 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

// you can also use includes, for example:
// #include <algorithm>

#include <algorithm>

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

    // Assume each number has 0 non dividers
    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;
}

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

✔