Archive for the ‘C++’ Category

Solution to the Codility Common Prime divisors Set Problem

This article discusses (a problem that I recently solved on codility ).

The core of the problem is the following:
Given two non negative integers N and M, , the task is to check whether they have the same set of prime divisors.
A prime divisor of an integer P is a prime d s.t. for some positive . You are given up to of such queries, and should return the total number of them that evaluates to true.

For instance given if and then our function should return *true* because the set of prime divisor of is equal the
the set of primal divisor of i.e. while for and the function should return *false*.

Smart (not enough) Brute Force approach

An easy approach in solving this problem could be computing by bruteforce the set of prime divisors of both numbers and compare them, and return true if they contains the same elements.
In order to achieve that we should:

  1. compute the set of primes up to . There are approximately (Read here for a more info on this topic https://primes.utm.edu/howmany.html)
  2. Using the Sieve of Έρατοσθένης approach we are able to compute it in time and space (see the following code).
  3. 
    void getPrimesSieve(vector<long long>&primes, const ll n) {
    using ll = long;
        vector<bool> nums(n + 1, true);
        primes.push_back(2);
        for (ll i = 3; i * i < n + 1; i += 2) {
            if (nums[i]) {
              for (ll j = i * i; j < n + 1; j += 2 * i) {
                 nums[j] = false;
                }
            }
        }
    
        for (ll i = 3 ; i <= n ; i += 2)
            if (nums[i])
                primes.push_back(i);
    }
    
  4. With the set of prime numbers in place then we can start finding the primal divisors. The following function computes the set of unique prime divisors of and stores them in .
  5. bool primalDivisors( long p , vector<long>& F, vector<long>& primes) {
     int i = 0;
     int c = 0;
     if (i >= primes[primes.size()-1])
                return false;
        while (p > 1) {        
            if (p % primes[i] == 0)
            {
                c++;
                p /= primes[i];
            }
            else 
            {
                if (c > 0) {
                    F.push_back(primes[i]);
                    c = 0;
                }
                i++;
            }
        }
        if (c > 0) 
            F.push_back(primes[i]);
        
        return true;
    }
    
  6. Finally we can iterate among all the queries and count the number of pairs returning *true*.
  7. int solution(vector<int>& A,vector<int>& B){
    	int LIM = -1;
    	int ans = 0;
    	LIM = max( *max_element(A.begin(), A.end()) ,*max_element(B.begin(), B.end()) ) ;
    	vector<int> primes;
    	getPrimesSieve(primes, LIM);
    
    	for (unsigned i = 0; i < A.size(); ++i)
    	{
    		vector<int> divA; 
    		vector<int> divB;
    		primalDivisors(A[i] , divA, primes);
    		primalDivisors(B[i] , divB, primes);
    		
    //same set of divisors
    		if( divA == divB)
    			ans++;
    
    	}
    	return ans;
    }
    

Altough this approach is correct, it is too slow. There are primes up to . Since the primalDivisors function gets called up to times and it has linear complexity then the overall time complexity is: which translates to !

Fast Approach using GCD

For two number to share the same set of prime divisors it must be the case that and . Checking if a number has a set of prime divisors that is subset of another is easy. In order for two number to have the same set of prime divisors the following must hold:
and i.e. their factorization only differ in the exponents.
Since clearly the we can divide by it obtaining . cannot have a larget set of factors than and hence its set of prime divisor is still contained into 's one. We can keep repeating this process until becomes one.
Dividing by the eliminates the common part of among the two number. And if eventually the dividend becomes , that means that the common part was the only part present.

As an example consider and , and . Repeting the process leads to and and and .
This shows that the set of prime divisor of M is contained in the set of prime divisor of N.
If we can show that the set of N is included in M's one, than the two sets must be equal. It is sufficient to do the same process with roles of N and M swapped.
If apply the same process to swapping the values of M and N from the previous example we obtain that and , and .

If there is a divisor that is not common to both number then the process will eventually isolate it.
Imagine that and . All common divisors will be cancelled out by repeting the division by the GCD leaving and .

Finally, the following is a possible implementation of the overall previous idea, which is also much simpler and cleaner than the one presented in the previous section.

bool containedSet(int M, int N){
	int g = __gcd(min(N,M), max(N,M));
    while(g != 1){
    	M /= g;
    	g = __gcd(min(N,M), max(N,M));
    }
    return M==1;
}


int solution(vector<int>& A,vector<int>& B){
	int ans = 0;
	for (unsigned i = 0; i < A.size(); ++i)
	{
	    //divisor A contained in divisor of B
	    //divisor A contained in divisor of A
	    //implies divisor A =  divisor of B	
           if(containedSet(A[i],B[i]) && containedSet(B[i],A[i]))
		ans++;

	}
	return ans;
}

Static and Dynamic Polymorphism - Curious Recurring Template Pattern and Mixin Classes

 A Few Words on Polymorphism

Polymorphism is the ability to assign a pointer to a base class to an instance of one its derived class. When a method is invoked on that pointer, the derived implementation, if provided, of the method is called otherwise, the inherited method is. The following is an example of such feature.

class Polygon {
  protected:
   double width, height;
  public:
   void Polygon(int a, int b) : width(a), height(b){};
  double area() const =0;
  int perimeter() const
   { return -1; }
};
};

class Rectangle: public Polygon {
public:
double area()
{ return width*height; }
int perimeter() const{ return width*2 + height*2;};
};

class Triangle: public Polygon {
public:
double area()
{ return width*height/2; }
};

int main () {
  Rectangle rect;
  Triangle trgl;
  Polygon * ppoly1 = &rect;
  Polygon * ppoly2 = &trgl;
  ppoly1->set_values (4,5);
  ppoly2->set_values (4,5);
  cout << rect.area() << '\n';
  cout << trgl.area() << '\n';
  return 0;
}

It is implemented with a cost in term of memory and time. For each class a virtual method table is stored and a pointer to it is added to the definition (transparently, by the compiler) of each class containing a virtual method (or deriving from a class that contains a virtual method). The table in turn contains pointer to the actual implementation of the virtual methods for the derived class. So the compiler only knows the object through a pointer to its base class, but it can still generate the correct code since it can indirect the calls to overridden methods via the virtual method table, then lookup for the method in the table and finally call it. So polymorphism comes at a cost of storing a virtual method table for each class, a pointer to it in each instance of a polymorphic class and two level in indirection when calling a virtual method.
Another pitfall is that since the indirection is required, usually virtual methods cannot be in-lined.

 

Curious Recurring Template Pattern

The key idea is: polymorphism without extra run-time cost. Static polymorphism.

Templates can mitigated performance problems of dynamic polymorphism via the so called static polymorphism, or simulated dynamic binding. Read On…