Lesson 9: CountNonDivisible (Count Non Divisible)

Lesson 9: CountNonDivisible
https://codility.com/programmers/lessons/9

(1) O(N * sqrt(N)) の解答

一番簡単な解法は、各数字の出現回数をまず調べておいて、その後A[i]それぞれにたいして、1からsqrt(A[i])までの数字で割り切れるかチェック。割れたら、割る数と割れた答えの出現回数をカウント に足して行きます。最終的にそれをNから引きます。

これで１００％の答えがもらえます。

しかしですが、1からsqrt(A[i])までのdivisorをチェックする部分は O(sqrt(N))の計算量なので、トータルではO(N * sqrt(N))の計算量の答えのはずです。

問題が要求しているのはO(N * log(N))の解答なので、別の答えを探さなければ…

#include<alloca.h>
#include<memory.h>

struct Results solution(int A[], int N) 
{
    //the number that may appear will be [1.. 2 * N].
    int size = sizeof(int) * (N * 2 + 1);    
    int* occurrence = (int*)alloca(size);
    memset(occurrence, 0x00, size);
        
    
    //allocate the memory for the result.
    struct Results result;
    result.C = (int*)calloc(N, sizeof(int));
    result.L = N;
        
    //now we check the array A and count the occurance for each number.
    int i,j;
    for (i = 0; i < N; i++){
        occurrence[A[i]]++;
    }
          
    //now we compute the answer.
    for (i = 0; i < N; i++){
        int num = A[i];

        int div_cnt = 0;
        
        //count the number of the divisor while doing factorization.
        for (j = 1; j * j < num; j++){
            if (num % j == 0){
                div_cnt += occurrence[j];
                div_cnt += occurrence[num / j];
            }
        };
        
        if (j * j == num){
            div_cnt += occurrence[j];
        }
        
        result.C[i] = N - div_cnt;
    }
    
    return result;

}

(1) O(N * log(N)) の解答

さて、O(N * log(N))の解法を見てみましょう。
まず、最初に1 to N * 2の間の数が、それぞれ配列Aに何回出現するかを配列occurrenceに格納するのは同じです。これはO(N)の計算量で出来ますね。

違いはここからです。

また1からN * 2の間の数字をチェックします。

最初に、配列answerを用意します。最終的にこの配列にはiの値に対する答えがanswer[i]に格納されることになります。ですからanswer[i]を見れば、iに対する答えが定数時間でわかることになりますね。

ここで、とりあえず全ての数にたいして答えがNであると仮定しましょう。言い換えればどの数字にもdivisorがないということです（実際には全部が全部素数でも、その数字自体 が必ずdivisorになるので、Nになることはないですね）。ここから、もしある数字iのdivisorが表れていれば、現在のanswer[i]の値から引いて行けば、最終的には、ただしいnon divisorの数が得られるという訳です。

では、今から配列occurrenceを頭から終わりまでスキャンして行きましょう。有る数字iが配列Aにあれば、対応するoccurrence[i]が０ならば無視、もし１以上であれば次のようにします。

occurrence[i]が１以上の場合、そのiからはじめてiの倍数の answerの要素から、そのoccurrence[i]の値を引いて行きます。つまりanswer[i],answer[i * 2], answer[i * 3], answer[i * 4]…からiの出現回数を引いて行くのです。

そうすると全ての可能なi (つまり問題の定義から1以上N * 2以下です）にたいしてこれを行うと最終的にanswer[i]にはnon divisorの数が入っています。

言い換えてみましょう。(1)の解答はある数が見つかったあとに、そのdivisorを毎回検索して、その出現回数をNから引いていました。今度は逆にあるiの倍数k(つまりkのdivisorの一つがiになります）にたいして、iの出現回数を引いて行くという逆の方針をとっています。

Lesson 8: Prime Numbers(Reversing coins, Lesson 8: Open reading material (PDF) を見ましょう)であるように、これはO(N * log(N))のアルゴリズムになります。

さて、全体の計算量を考えてみましょう。まず最初のoccurrence配列を作るのはO(N)ですね。そして上のアルゴリズムはO(N * log(N))です。ということは、この二つをあわせると大きい方をとってO(N * log(N))のアルゴリズムとなりますね。そして最後に配列answerから解答を一つ取るのは定数時間ですから、それをN回繰り返すと、O(N)の計算量ですよね。これをO(N * log(N))とあわせると大きい方を取るのでO(N * log(N))のままですね。
ですから、全体ではO(N * log(N))の計算量ということになりますね。

#include<alloca.h>
#include<memory.h>

struct Results solution(int A[], int N) 
{
    //the number that may appear will be [1 ... 2 * N].
    int size = sizeof(int) * (N * 2 + 1);    
    int* occurrence = (int*)alloca(size);
    memset(occurrence, 0x00, size);
    
    //the space to hold the answer for each value from 1 ... 2 * N.
    //for now we initialize it 
    int* answer = (int*)alloca(size);
    memset(answer, 0x00, size);
    
    
    //allocate the memory for the result.
    struct Results result;
    result.C = (int*)calloc(N, sizeof(int));
    result.L = N;
        
    //now we check the array A and count the occurance for each number.
    int i;
    for (i = 0; i < N; i++){
        occurrence[A[i]]++;
    }
        
    //now we compute the answer.
    for (i = 1; i <= N * 2; i++){
        int num = occurrence[i];
        
        //the number doesn't in the array A, we can neglect it.
        if (num == 0){
            continue;
        }

        //if it appears in the array A, 
        //subtract its counts from cells at itss multiples in the answer array.
        int j;
        for (j = i; j <= N * 2; j += i){
            answer[j] -= num;
        }        
    }
    
    //as the answer array contains the offset to N, 
    //N + answer[A[i]] will give the answer for each.
    for (i = 0; i < N; i++){
        result.C[i] = N + answer[A[i]];
    }
    
    return result;
}