Lesson 10: CommonPrimeDivisors (Common Prime Divisors)

Lesson 10: CommonPrimeDivisors (Common Prime Divisors)
https://codility.com/programmers/lessons/10

As this problem requires the space complexity of O(1), it is suggested that the factorization algorithm that we learned in Lesson 9 can't be used. 

I took the strategy as follows. 

Suppose two number N and M, and factorize them by prime numbers, and then express the GCD of N and M as P1 * P2 * P3 * P4 * ... Px (each of these are prime divisors of gcd(N,M)). Then , express N / gcd(N,M) and M / gcd(N,M) as N1 * N2 * N3 * ... Ny, and M1 * M2 * M3 * ... Mz, by their prime divisors respectively; then, N and M can be expressed as below.

N = (P1 * P2 * P3 ... Px) * N1 * N2 * N3 * ... Ny
M = (P1 * P2 * P3 ... Px) * M1 * M2 * M3 * ... Mz 

Since (P1 * P2 * P3 ... Px) is the gcd(N,M), Any prime divisor common to N and M is always appear at least once among (P1, P2, P3, ... Px). 

In other words, if any prime divisor of 'N/ gcd(N,M)' (N1, N2, N3 ... Ny) can't be found among (P1, P2, P3, ...Px), it is not a prime divisor of M. Thus, it can be said that the set of prime divisors of N and M are not exactly the same.

Similarly, if any prime divisor of 'M / gcd(A,B)' (M1, M2, L3 ... Ly) can't be found among (P1, P2. P3, ... Px), it is not a prime divisor of N and it can be said that the set of prime divisors of N and M are not exactly the same.

So the problem is just to check if any of N1-Ny and M1-Mz never appears in P1-Px. 

Now let's think of this. Let X = N / gcd(N,M) and consider gcd(gcd(N, M), X).

For now, it will be as follows.

gcd(N,M): P1 * P2 * P3 ... Px
X       : N1 * N2 * N3 ... Ny

If gcd(N,M) % X == 0, then all the prime divisors of X is included in gcd(N,M).

If not, then we compute gcd(gcd(N,M), X). If the gcd of these two values are just 1, that means none of N1-Ny appears in P1-Px; which means the value N have a prime divisor that is not shared with M.

If the gcd larger than 1. then we compute X / gcd(gcd(N,M), X), and update X with this for the next round. This means we took out some of prime divisors of X, which constitutes gcd(gcd(N,M), X), and use it for the next round

If gcd(N, M) % X == 0 at this point, that means all the prime divisors of X is included in gcd(N, M). If not, we do the same thing again as above.


Let's show it more concretely. 
Suppose two number 

N:3 * 5 * 3 * 7
M:3 * 5 * 11 * 13

Then, 
gcd(N, M): 3 * 5
X        : 3 * 7

Since 15 % 21 != 0, we need to do more.

Now, gcd(gcd(N, M), X) = 3. Then,

X / gcd(gcd(N, M), X) = 3 * 7 / 3 = 7. This will be X in the next round.

Then,
gcd(N, M): 3 * 5
X        : 7

Now, gcd(gcd(N, M), X) = 1. Thus, N has a prime divisor that M doesn't have. (If M has 7 as its prime divisor, 7 must be included in gcd(N, M) as its prime divisor).


If we do the same to M, we can check if N and M have the exactly the same set of prime divisors.



Now let's check if this algorithm suffices the worst-case time complexity of O(Z*log(max(A)+max(B))^2) as specified by the problem. This time we use the simple O(log(a+b)) algorithm to compute gcd(a,b). 

The above algorithm compute gcd(a,b) once in one round and repeats the method less than log (a) times. 

For instance, assume gcd(N,M) = 2 and N = 2 * 2 * 2 * 2 * 2, using the smallest possible prime divisor 2. As N is composed of five 2s, `rest / gcd(gcd(N,M),X)' must be repeated 4 times until it becomes gcd(N,M) % rest == 0.

So the time complexity of this algorithm does not exceed O(log(N+M) * log(N)). Similarly, the part to perform the same to M, the time complexity does not exceed O(log(N+M)*log(M)).

So the time complexity after combining these two parts (to perform the above algorithms N and M), doesn't exceed O(log(N+M)*log(N)+log(N+M)*log(M)).

Then, since log(N) < log(N+M) and log(M) < log(N+M),
log(N+M) * log(N) + log(N+M) * log(M) <= 2 * log(N+M) * log(N+M).

So the time complexity to perform this algorithm doesn't exceed O(2 * log(N+M) * log(N+M)). The constant 2 can be removed and then O(log(N+M)^2). 

We have to repeat this for each A[i] and B[i] for Z times. The worst case we can assume for the whole program doesn't exceed O(Z * log(max(A)+max(B))^2), as required by the program.

As below, this algorithm gives the 100% score.

//The O (log(a + b)) gcd algorithm,

int gcd(int a, int b)

{

    if (a % b == 0){

        return b;;

    }

    return gcd(b, a % b);

}

int check(int a, int gcd_ab)

{

    //check if all the prime divisors of 'a' can be found

    //in the prime divisors of gcd(a,b).

    int rest = a / gcd_ab;

    

    //if gcd(a, b) % rest == 0, that means all the prime divisors 

    //of 'rest' is included in the prime divisors of gcd(a,b).

    while (gcd_ab % rest != 0){

        int gcd_tmp = gcd(gcd_ab, rest);

        

        //if gcd(a,b) have 1 as the gcd with rest larger,

        //that means 'a / gcd(a,b)' contains some prime divisor that is not

        //found in the prime divisors of gcd(a,b).
        if (gcd_tmp == 1){

            return 0;

        }

        

        rest /= gcd_tmp;

    }

    

    return 1;

}

int solution(int A[], int B[], int Z) 

{

    int cnt = 0;

    

    int i;

    for (i = 0; i < Z; i++){

        int gcd_ab = gcd(A[i], B[i]);

        if (check(A[i], gcd_ab) && check(B[i], gcd_ab)){

            cnt++;

        }

    }

    

    return cnt;

}