Task
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 prime D is called a prime divisor of a positive integer P if there exists a positive integer K such that D * K = P. For example, 2 and 5 are prime divisors of 20.
You are given two positive integers N and M. The goal is to check whether the sets of prime divisors of integers N and M are exactly the same.
Write a function:
int solution(vector<int> &A, vector<int> &B);that, given two non-empty arrays A and B of Z integers, returns the number of positions K for which the prime divisors of A[K] and B[K] are exactly the same.
Write an efficient algorithm for the following assumptions:
- Z is an integer within the range [1..6,000];
- each element of arrays A, B is an integer within the range [1..2,147,483,647].
Solution
The solution is based on the observation that if all the prime factors of Y are factors of X, then Y/gcd(X,Y) will be 1 or also contain only factors of X.
So the result can be found by repeatedly reducing Y by gcd(X,Y) to find if all the factors of Y are in X.
#include <cassert>
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
// calculate greatest common divisor using euclidean method
int calcGcd(int x, int y) {
if (y == 0) return x;
if (x < y) {
return calcGcd(x, y % x);
} else {
if (x > y) {
return calcGcd(y, x % y);
} else {
return x;
}
}
}
// returns true if and only if all prime factors of y are in x
bool allYFactorsInX(int x, int y) {
if (x == y)
return true;
// y has all factors in x, if and only if y/gcd(x,y) does
int gcd = calcGcd(x, y);
// if reached 1, last value was not a common factor
if (gcd == 1)
return false;
// y divides x, so true
if (gcd == y)
return true;
return allYFactorsInX(x, y / gcd);
}
int solution(vector<int> &A, vector<int> &B) {
size_t siz = A.size();
assert(B.size() == siz);
int res = 0;
for (size_t i = 0; i < siz; i++) {
if (allYFactorsInX(A[i], B[i]) && allYFactorsInX(B[i], A[i]))
res++;
}
return res;
}Test Function
This code tests the solution
void check(vector<int> P, vector<int> Q, int expected) {
int res = solution(P, Q);
assert(res == expected);
}
int main() {
assert(calcGcd(15, 10) == 5);
assert(calcGcd(15, 75) == 15);
assert(calcGcd(9, 75) == 3);
assert(calcGcd(9, 1) == 1);
assert(calcGcd(9, 9) == 9);
check({15, 10, 3}, {75, 30, 5}, 1);
check({45}, {75}, 1);
check({2147483647}, {2147483647}, 1);
check({2147483647}, {3}, 0);
check({2, 1, 2}, {1, 2, 2}, 1);
check(
{
48, 66, 67, 15, 2, 38, 28, 82, 70, 61, 56, 67, 15, 45, 17, 91, 6, 82, 8, 69, 34, 41, 85, 2, 7,
92, 51, 10, 99, 95, 12, 43, 14, 32, 63, 17, 70, 6, 18, 82, 41, 42, 60, 48, 39, 4, 73, 97, 98, 67,
36, 37, 70, 68, 12, 24, 37, 52, 82, 51, 3, 83, 44, 52, 23, 43, 39, 78, 11, 55, 18, 70, 4, 28, 35,
64, 6, 46, 21, 29, 48, 96, 49, 96, 17, 93, 37, 19, 75, 92, 1, 27, 78, 35, 25, 1, 5, 62, 99, 100,
},
{
97, 2, 74, 16, 99, 2, 88, 69, 86, 100, 24, 34, 71, 29, 27, 23, 86, 88, 80, 23, 93, 52, 24, 46, 42,
8, 57, 36, 57, 94, 65, 41, 87, 100, 50, 95, 2, 15, 18, 94, 70, 72, 29, 50, 89, 10, 12, 5, 47, 85,
56, 41, 51, 18, 95, 36, 24, 32, 83, 32, 91, 34, 45, 8, 91, 80, 48, 12, 50, 38, 85, 93, 75, 29, 5,
90, 95, 16, 50, 49, 98, 5, 7, 85, 57, 47, 78, 60, 70, 26, 9, 1, 34, 65, 38, 35, 62, 71, 60, 32,
},
3);
check(
{
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
},
{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
},
18);
check(
{
7,
17,
5,
3,
},
{
7,
11,
5,
2,
},
2);
check(
{
121,
8,
25,
81,
49,
},
{
11,
4,
125,
11,
7,
},
4);
}Results
Codility Results
| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(Z * log(max(A) + max(B))2) |