Test results - Codility

Tasks Details

medium

1. CommonPrimeDivisors

Check whether two numbers have the same prime divisors.

100%

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.

For example, given:

N = 15 and M = 75, the prime divisors are the same: {3, 5};

N = 10 and M = 30, the prime divisors aren't the same: {2, 5} is not equal to {2, 3, 5};

N = 9 and M = 5, the prime divisors aren't the same: {3} is not equal to {5}.

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.

For example, given:

A[0] = 15 B[0] = 75 A[1] = 10 B[1] = 30 A[2] = 3 B[2] = 5

the function should return 1, because only one pair (15, 75) has the same set of prime divisors.

Write an efficient algorithm for the following assumptions:

Z is an integer within the range [1..6,000];

each element of arrays A and B is an integer within the range [1..2,147,483,647].

Solution

Programming language used C++

Time spent on task 1 minutes

Notes

not defined yet

Task timeline

Code: 14:09:45 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 43 44

#include <cassert>
#include <iostream>
#include <math.h>
#include <vector>
// 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;
}

Analysis

▶

example
example test

✔

Code: 14:09:51 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 43 44

#include <cassert>
#include <iostream>
#include <math.h>
#include <vector>
// 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;
}

Analysis

▶

example
example test

✔

Code: 14:09:54 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 43 44

#include <cassert>
#include <iostream>
#include <math.h>
#include <vector>
// 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;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(Z * log(max(A) + max(B))**2)

▶

example
example test

✔

▶

extreme
extreme test with small values

✔

▶

simple_1
simple test with small values

✔

▶

simple_2
simple test with small values

✔

▶

primes
powers of primes

✔

▶

small_primes
small primes

✔

▶

small_all_pairs
all pairs 1-10, length = 100

✔

▶

small_random
small random test, length = 100

✔

▶

large_all_pairs
all pairs 1-70, length = ~5,000

✔

▶

large_random
large random tests, length = ~6,000

✔

▶

many_factors
factorial test

✔

▶

many_factors2
factorial test

✔

▶

big_powers
powers of 2 and 3

✔

▶

extreme_maximal
extreme test with maximal values

✔