Minimum removals from array to make GCD Greater in C++

Concept

With respect of given N numbers, the target is to determine the minimum removal of numbers such that GCD of the remaining numbers is larger than initial GCD of N numbers. If it is impossible to increase the GCD, print “NO”.

Input 

b[] = {1, 2, 4}

Output

1

After removing the first element, then the new GCD is 2, which is larger than the initialGCD i.e., 1.

Input 

b[] = {6, 9, 15, 30}

Output 

3

The initial gcd is 3, after removing 6 and 9 to obtain a gcd of 15 which is larger than 3. We can also remove 9 and 15 to get a gcd of 6.

Method

We should follow the following steps to solve the above problem −

• At first we should determine the gcd of N numbers applying Euclidean algorithms.

• We should divide all numbers by the determined gcd.

• Applying prime factorization for multiple queries technique, we should determinethe prime factorization of every number in O(log N).

• We have to insert all the prime factors in the set to eliminate duplicates whichare obtained applying this method.

• Applying a hash-map method, we should count the frequencies of the prime factors in every i-th element.

• At the time when the factorization of numbers have been performed, and the counthas been stored in the frequency table, iterate in the hash-map and determinethe prime factor which occurs the largest number of times. This prime factor cannot be N, because we have already divided the array elements initially by the initial gcd of N numbers.

• As a result,the number of removals will always be N-(hash[prime_factor]) if thereare any such factors after division of initial gcd.

Example

 Live Demo

// This C++ program finds the minimum removals // so that the calculated gcd of remaining numbers will be more // than the initial gcd of N numbers #include <bits/stdc++.h> using namespace std; #define MAXN 100001 // storing smallest prime factor for every number int spf1[MAXN]; // Calculates SPF (Smallest Prime Factor) for every // number till MAXN. // Time Complexity : O(nloglogn) void sieve1(){    spf1[1] = 1;    for (int i = 2; i < MAXN; i++)       // marks smallest prime factor for every       // number to be itself.    spf1[i] = i;    // separately marks spf for every even    // number as 2    for (int i = 4; i < MAXN; i += 2)       spf1[i] = 2;    for (int i = 3; i * i < MAXN; i++) {       // checks if i is prime       if (spf1[i] == i) {          // marks SPF for all numbers divisible by i          for (int j = i * i; j < MAXN; j += i)             // marks spf1[j] if it is not             // previously marked             if (spf1[j] == j)                spf1[j] = i;       }    } } // Now a O(log n) function returning primefactorization // by dividing by smallest prime factor at every step vector<int> getFactorization1(int x){    vector<int> ret;    while (x != 1) {       ret.push_back(spf1[x]);       x = x / spf1[x];    }    return ret; } // So function which returns the minimal // removals required to make gcd // greater than previous int minimumRemovals1(int a1[], int n){    int g = 0;    // finding initial gcd    for (int i = 0; i < n; i++)       g = __gcd(a1[i], g);    unordered_map<int, int> mpp;    // divides all number by initial gcd    for (int i = 0; i < n; i++)       a1[i] = a1[i] / g;    // iterating for all numbers    for (int i = 0; i < n; i++) {       // primt factorisation to get the prime       // factors of i-th element in the array       vector<int> p = getFactorization1(a1[i]);       set<int> s1;       // insert all the prime factors in       // set to remove duplicates       for (int j = 0; j < p.size(); j++) {          s1.insert(p[j]);       }       /// increase the count of prime       // factor in map for every element       for (auto it = s1.begin(); it != s1.end(); it++) {          int el = *it;          mpp[el] += 1;       }    }    int mini = INT_MAX;    int mini1 = INT_MAX;    // iterate in map and check for every factor    // and its count    for (auto it = mpp.begin(); it != mpp.end(); it++) {       int fir1 = it->first;       int sec1 = it->second;       // checking largest appearing factor       // which does not appears in any one or more       if ((n - sec1) <= mini) {          mini = n - sec1;       }    }    if (mini != INT_MAX)       return mini;    else       return -1; } // Driver code int main(){    int a1[] = { 6, 9, 15, 30 };    int n = sizeof(a1) / sizeof(a1[0]);    sieve1();    cout << minimumRemovals1(a1, n);    return 0; }

Output

2