अवधारणा
दिए गए एन नंबरों के संबंध में, लक्ष्य न्यूनतम संख्या को हटाने का निर्धारण करना है ताकि शेष संख्याओं का जीसीडी एन संख्याओं के प्रारंभिक जीसीडी से बड़ा हो। यदि GCD को बढ़ाना असंभव है, तो "NO" प्रिंट करें।
इनपुट
b[] = {1, 2, 4} आउटपुट
1
पहले एलिमेंट को हटाने के बाद, नया GCD 2 होता है, जो कि शुरुआतीGCD यानी 1 से बड़ा होता है।
इनपुट
b[] = {6, 9, 15, 30} आउटपुट
3
प्रारंभिक gcd 3 है, 15 का gcd प्राप्त करने के लिए 6 और 9 को हटाने के बाद, जो 3 से बड़ा है। हम 6 का gcd प्राप्त करने के लिए 9 और 15 को भी हटा सकते हैं।
विधि
उपरोक्त समस्या को हल करने के लिए हमें निम्नलिखित चरणों का पालन करना चाहिए -
-
सबसे पहले हमें यूक्लिडियन एल्गोरिदम को लागू करने वाले एन नंबरों की जीसीडी निर्धारित करनी चाहिए।
-
हमें सभी संख्याओं को निर्धारित gcd से भाग देना चाहिए।
-
मल्टीपल क्वेश्चन तकनीक के लिए अभाज्य गुणनखंडन लागू करते हुए, हमें O(log N) में प्रत्येक संख्या का अभाज्य गुणनखंड निर्धारित करना चाहिए।
-
हमें इस पद्धति का उपयोग करके प्राप्त होने वाले डुप्लिकेट को खत्म करने के लिए सेट में सभी प्रमुख कारकों को सम्मिलित करना होगा।
-
हैश-मैप पद्धति को लागू करते हुए, हमें प्रत्येक i-वें तत्व में अभाज्य गुणनखंडों की आवृत्तियों की गणना करनी चाहिए।
-
उस समय जब संख्याओं का गुणनखंडन किया जाता है, और गिनती को आवृत्ति तालिका में संग्रहीत किया जाता है, हैश-मैप में पुनरावृति होती है और सबसे बड़ी संख्या में होने वाले प्रमुख कारक का निर्धारण करती है। यह अभाज्य गुणनखंड N नहीं हो सकता, क्योंकि हमने पहले ही सरणी तत्वों को N संख्याओं के आरंभिक gcd से विभाजित कर दिया है।
-
परिणामस्वरूप, यदि प्रारंभिक gcd के विभाजन के बाद ऐसे कोई कारक हैं, तो निष्कासन की संख्या हमेशा N-(hash[prime_factor]) होगी।
उदाहरण
// 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;
} आउटपुट
2
