Codility Lesson 11

11.1 - Count Non Divisible

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:

class Solution 
{
  public int[] solution(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 an array 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].

using System;
using System.Linq;
using System.Collections.Generic;

/**
 * 11.1 - Count Non Divisible
 */
class Solution {
    public int[] solution(int[] A) {


        var ans = new int[A.Length];

        /*
         * Count the number of occurrences
         */
        var max = A.Max();
        var cnt = new int[max + 1];
        for(var i = 0; i < A.Length; i++) 
            cnt[A[i]] += 1;

        /*
         * Count the number of divisors
         */
        for (int i = 0; i < A.Length; i++)
        {
            /*
             * Calculate 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 += cnt[j];
                    if (A[i] / j != j)
                        divisors += cnt[A[i] / j];
                }

            /*
             * Subtract the number of divisors 
             * from the number of elements in the array
             */
            ans[i] = A.Length - divisors;
        }

        return ans;
    }
}

---

11.2 - Count Semi Primes

A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.

A semiprime is a natural number that is the product of two (not necessarily distinct) prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

You are given two non-empty arrays P and Q, each consisting of M integers. These arrays represent queries about the number of semiprimes within specified ranges.

Query K requires you to find the number of semiprimes within the range (P[K], Q[K]), where 1 ≤ P[K] ≤ Q[K] ≤ N.

For example, consider an integer N = 26 and arrays P, Q such that:

    P[0] = 1    Q[0] = 26
    P[1] = 4    Q[1] = 10
    P[2] = 16   Q[2] = 20

The number of semiprimes within each of these ranges is as follows:

• (1, 26) is 10,
• (4, 10) is 4,
• (16, 20) is 0.

Write a function:

class Solution 
{
  public int[] solution(int N, int[] P, int[] Q); 
}

that, given an integer N and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M elements specifying the consecutive answers to all the queries.

For example, given an integer N = 26 and arrays P, Q such that:

    P[0] = 1    Q[0] = 26
    P[1] = 4    Q[1] = 10
    P[2] = 16   Q[2] = 20

the function should return the values [10, 4, 0], as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..50,000];
• M is an integer within the range [1..30,000];
• each element of arrays P and Q is an integer within the range [1..N];
• P[i] ≤ Q[i].

using System;
using System.Linq;
using System.Collections.Generic;

/**
 * 11.2 - Count Semi Primes
 * Paulo Santos
 * 19.Dec.2022
 */
class Solution {
    public int[] solution(int N, int[] P, int[] Q) {

        /*
         * Calculate all the primes up to (N / 2 + 1);
         */
        var primes = new List<int>();
        var sieve = new bool[N / 2 + 2];
        sieve[0] = sieve[1] = true;
        for(var i = 2; i < sieve.Length; i++) {
            for(var j = i * i; j < sieve.Length; j += i) {
                sieve[j] = true;
            }
        }
        for(var i = 0; i < sieve.Length; i++) 
            if (!sieve[i])
                primes.Add(i);
        

        /*
         * Calculate all the semi-primes
         */
        var semi = new int[N + 1];
        for (var i = 0; i < primes.Count; i++) 
            for (var j = 0; j < primes.Count; j++) {
                var sp = primes[i] * primes[j];
                if (sp <= N)
                    semi[sp] = 1;
            }
        var aux1 = new int[N + 1];
        for (var i = 1; i < N + 1; i++)
            aux1[i] = semi[i] + aux1[i - 1];
        
        /*
         * Count the semi-primes
         */
        var res = new int[P.Length];
        for(var i = 0; i < res.Length; i++)
            res[i] = aux1[Q[i]] - aux1[P[i] - 1];
        
        return res;
    }
}