Given N numbers, the task is to find the minimum removal of numbers such that the GCD of the remaining numbers is greater than the initial GCD of N numbers. If it is not possible to increase the GCD, print “NO”.
Examples:
Input: a[] = {1, 2, 4}
Output: 1
Remove the first element, then the new GCD is 2, which is greater than the initial GCD i.e., 1.Input: a[] = {6, 9, 15, 30}
Output: 2
The initial gcd is 3, remove 6 and 9 to obtain a gcd of 15 which is greater than 3. You can also remove 9 and 15 to get a gcd of 6.
The following steps are followed to solve the above problem:
- Initially find the gcd of N numbers using Euclidean algorithms.
- Divide all numbers by the obtained gcd.
- Using prime factorization for multiple queries method, find the prime factorization of every number in O(log N). The method can be read here.
- Insert all the prime factors in the set to remove duplicates that are obtained using this method.
- Using a hash-map, count the frequencies of the prime factors in every i-th element.
- Once the factorization of numbers has been done, and the count has been stored in the frequency table, iterate in the hash-map and find out the prime factor which occurs the maximum number of times. It cannot be N, as we have already divided the array elements initially by the initial gcd of N numbers.
- The number of removals will always be n-(hash[prime_factor]) if there are any such factors after the division of initial gcd.
Implementation:
C++
// C++ program to find the minimum removals// such that gcd of remaining numbers is more// than the initial gcd of N numbers#include <bits/stdc++.h>using namespace std;#define MAXN 100001// stores smallest prime factor for every numberint spf[MAXN];// Calculating SPF (Smallest Prime Factor) for every// number till MAXN.// Time Complexity : O(nloglogn)void sieve(){ spf[1] = 1; for (int i = 2; i < MAXN; i++) // marking smallest prime factor for every // number to be itself. spf[i] = i; // separately marking spf for every even // number as 2 for (int i = 4; i < MAXN; i += 2) spf[i] = 2; for (int i = 3; i * i < MAXN; i++) { // checking if i is prime if (spf[i] == i) { // marking SPF for all numbers divisible by i for (int j = i * i; j < MAXN; j += i) // marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } }}// A O(log n) function returning primefactorization// by dividing by smallest prime factor at every stepvector<int> getFactorization(int x){ vector<int> ret; while (x != 1) { ret.push_back(spf[x]); x = x / spf[x]; } return ret;}// Function which returns the minimal// removals required to make gcd// greater than previousint minimumRemovals(int a[], int n){ int g = 0; // finding initial gcd for (int i = 0; i < n; i++) g = __gcd(a[i], g); unordered_map<int, int> mpp; // divides all number by initial gcd for (int i = 0; i < n; i++) a[i] = a[i] / g; // iterating for all numbers for (int i = 0; i < n; i++) { // prime factorisation to get the prime // factors of i-th element in the array vector<int> p = getFactorization(a[i]); set<int> s; // insert all the prime factors in // set to remove duplicates for (int j = 0; j < p.size(); j++) { s.insert(p[j]); } /// increase the count of prime // factor in map for every element for (auto it = s.begin(); it != s.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 fir = it->first; int sec = it->second; // check for the largest appearing factor // which does not appears in any one or more if ((n - sec) <= mini) { mini = n - sec; } } if (mini != INT_MAX) return mini; else return -1;}// Driver codeint main(){ int a[] = { 6, 9, 15, 30 }; int n = sizeof(a) / sizeof(a[0]); sieve(); cout << minimumRemovals(a, n); return 0;} |
Java
// Java program to find the minimum removals// such that gcd of remaining numbers is more// than the initial gcd of N numbersimport java.util.*;class GFG{static final int MAXN = 100001;// stores smallest prime factor for every numberstatic int []spf = new int[MAXN];// Calculating SPF (Smallest Prime Factor)// for every number till MAXN.// Time Complexity : O(nloglogn)static void sieve(){ spf[1] = 1; for(int i = 2; i < MAXN; i++) // Marking smallest prime factor // for every number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for(int i = 4; i < MAXN; i += 2) spf[i] = 2; for(int i = 3; i * i < MAXN; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all numbers // divisible by i for(int j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } }}// A O(log n) function returning primefactorization// by dividing by smallest prime factor at every stepstatic Vector<Integer> getFactorization(int x){ Vector<Integer> ret = new Vector<>(); while (x != 1) { ret.add(spf[x]); x = x / spf[x]; } return ret;}// Recursive function to return gcd of a and b static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); }// Function which returns the minimal// removals required to make gcd// greater than previousstatic int minimumRemovals(int a[], int n){ int g = 0; // Finding initial gcd for(int i = 0; i < n; i++) g = __gcd(a[i], g); HashMap<Integer, Integer> mpp = new HashMap<>(); // Divides all number by initial gcd for(int i = 0; i < n; i++) a[i] = a[i] / g; // Iterating for all numbers for(int i = 0; i < n; i++) { // Prime factorisation to get the prime // factors of i-th element in the array Vector<Integer> p = getFactorization(a[i]); HashSet<Integer> s = new HashSet<>(); // Insert all the prime factors in // set to remove duplicates for(int j = 0; j < p.size(); j++) { s.add(p.get(j)); } // Increase the count of prime // factor in map for every element for(int it: s) { int el = it; if (mpp.containsKey(el)) { mpp.put(el, mpp.get(el) + 1); } else { mpp.put(el, 1); } } } int mini = Integer.MAX_VALUE; int mini1 = Integer.MAX_VALUE; // Iterate in map and check for // every factor and its count for(Map.Entry<Integer, Integer> it : mpp.entrySet()) { int fir = it.getKey(); int sec = it.getValue(); // Check for the largest appearing factor // which does not appears in any one or more if ((n - sec) <= mini) { mini = n - sec; } } if (mini != Integer.MAX_VALUE) return mini; else return -1;}// Driver codepublic static void main(String[] args){ int a[] = { 6, 9, 15, 30 }; int n = a.length; sieve(); System.out.print(minimumRemovals(a, n));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to find the minimum removals# such that gcd of remaining numbers is more# than the initial gcd of N numbersfrom math import gcd as __gcdMAXN = 100001# stores smallest prime factor for every numberspf = [i for i in range(MAXN)]# Calculating SPF (Smallest Prime Factor) for every# number till MAXN.# Time Complexity : O(nloglogn)def sieve(): # separately marking spf for every even # number as 2 for i in range(4, MAXN, 2): spf[i] = 2 for i in range(3, MAXN): if i * i > MAXN: break # checking if i is prime if (spf[i] == i): # marking SPF for all numbers divisible by i for j in range(2 * i, MAXN, i): # marking spf[j] if it is not # previously marked if (spf[j] == j): spf[j] = i# A O(log n) function returning primefactorization# by dividing by smallest prime factor at every stepdef getFactorization(x): ret = [] while (x != 1): ret.append(spf[x]) x = x // spf[x] return ret# Function which returns the minimal# removals required to make gcd# greater than previousdef minimumRemovals(a, n): g = 0 # finding initial gcd for i in range(n): g = __gcd(a[i], g) mpp = dict() # divides all number by initial gcd for i in range(n): a[i] = a[i] // g # iterating for all numbers for i in range(n): # prime factorisation to get the prime # factors of i-th element in the array p = getFactorization(a[i]) s = dict() # insert all the prime factors in # set to remove duplicates for j in range(len(p)): s[p[j]] = 1 # increase the count of prime # factor in map for every element for i in s: mpp[i] = mpp.get(i, 0) + 1 mini = 10**9 mini1 = 10**9 # iterate in map and check for every factor # and its count for i in mpp: fir = i sec = mpp[i] # check for the largest appearing factor # which does not appears in any one or more if ((n - sec) <= mini): mini = n - sec if (mini != 10**9): return mini else: return -1# Driver codea = [6, 9, 15, 30]n = len(a)sieve()print(minimumRemovals(a, n))# This code is contributed by mohit kumar 29 |
C#
// C# program to find the minimum // removals such that gcd of remaining // numbers is more than the initial // gcd of N numbersusing System;using System.Collections.Generic;class GFG{static readonly int MAXN = 100001;// stores smallest prime // factor for every numberstatic int []spf = new int[MAXN];// Calculating SPF (Smallest // Prime Factor) for every // number till MAXN. // Time Complexity : O(nloglogn)static void sieve(){ spf[1] = 1; for(int i = 2; i < MAXN; i++) // Marking smallest prime factor // for every number to be itself spf[i] = i; // Separately marking spf for // every even number as 2 for(int i = 4; i < MAXN; i += 2) spf[i] = 2; for(int i = 3; i * i < MAXN; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all numbers // divisible by i for(int j = i * i; j < MAXN; j += i) // Marking spf[j] if it is // not previously marked if (spf[j] == j) spf[j] = i; } }}// A O(log n) function returning // primefactorization by dividing // by smallest prime factor at // every stepstatic List<int> getFactorization(int x){ List<int> ret = new List<int>(); while (x != 1) { ret.Add(spf[x]); x = x / spf[x]; } return ret;}// Recursive function to// return gcd of a and b static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); }// Function which returns the // minimal removals required // to make gcd greater than // previousstatic int minimumRemovals(int []a, int n){ int g = 0; // Finding initial gcd for(int i = 0; i < n; i++) g = __gcd(a[i], g); Dictionary<int, int> mpp = new Dictionary<int, int>(); // Divides all number by // initial gcd for(int i = 0; i < n; i++) a[i] = a[i] / g; // Iterating for all numbers for(int i = 0; i < n; i++) { // Prime factorisation to get the prime // factors of i-th element in the array List<int> p = getFactorization(a[i]); HashSet<int> s = new HashSet<int>(); // Insert all the prime factors in // set to remove duplicates for(int j = 0; j < p.Count; j++) { s.Add(p[j]); } // Increase the count of prime // factor in map for every // element foreach(int it in s) { int el = it; if (mpp.ContainsKey(el)) { mpp[el]= mpp[el] + 1; } else { mpp.Add(el, 1); } } } int mini = int.MaxValue; int mini1 = int.MaxValue; // Iterate in map and check for // every factor and its count foreach(KeyValuePair<int, int> it in mpp) { int fir = it.Key; int sec = it.Value; // Check for the largest appearing // factor which does not appears // in any one or more if ((n - sec) <= mini) { mini = n - sec; } } if (mini != int.MaxValue) return mini; else return -1;}// Driver codepublic static void Main(String[] args){ int []a = {6, 9, 15, 30}; int n = a.Length; sieve(); Console.Write(minimumRemovals(a, n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to find the minimum removals// such that gcd of remaining numbers is more// than the initial gcd of N numberslet MAXN = 100001;// stores smallest prime factor for every numberlet spf = new Array(MAXN);// Calculating SPF (Smallest Prime Factor)// for every number till MAXN.// Time Complexity : O(nloglogn)function sieve(){ spf[1] = 1; for(let i = 2; i < MAXN; i++) // Marking smallest prime factor // for every number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for(let i = 4; i < MAXN; i += 2) spf[i] = 2; for(let i = 3; i * i < MAXN; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all numbers // divisible by i for(let j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } }}// A O(log n) function returning primefactorization// by dividing by smallest prime factor at every stepfunction getFactorization(x){ let ret = []; while (x != 1) { ret.push(spf[x]); x = x / spf[x]; } return ret;}// Recursive function to return gcd of a and b function __gcd(a,b){ return b == 0 ? a : __gcd(b, a % b);}// Function which returns the minimal// removals required to make gcd// greater than previousfunction minimumRemovals(a,n){ let g = 0; // Finding initial gcd for(let i = 0; i < n; i++) g = __gcd(a[i], g); let mpp = new Map(); // Divides all number by initial gcd for(let i = 0; i < n; i++) a[i] = a[i] / g; // Iterating for all numbers for(let i = 0; i < n; i++) { // Prime factorisation to get the prime // factors of i-th element in the array let p = getFactorization(a[i]); let s = new Set(); // Insert all the prime factors in // set to remove duplicates for(let j = 0; j < p.length; j++) { s.add(p[j]); } // Increase the count of prime // factor in map for every element for(let it of s.values()) { let el = it; if (mpp.has(el)) { mpp.set(el, mpp.get(el) + 1); } else { mpp.set(el, 1); } } } let mini = Number.MAX_VALUE; let mini1 = Number.MAX_VALUE; // Iterate in map and check for // every factor and its count for(let [key, value] of mpp.entries()) { let fir = key; let sec = value; // Check for the largest appearing factor // which does not appears in any one or more if ((n - sec) <= mini) { mini = n - sec; } } if (mini != Number.MAX_VALUE) return mini; else return -1;}// Driver codelet a = [6, 9, 15, 30];let n = a.length;sieve();document.write(minimumRemovals(a, n)); // This code is contributed by unknown2108</script> |
Output
2
Complexity Analysis:
- Time Complexity: O(log log N) for precalculation of Sieve, and O(N * log N) for calculation.
- Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
