अवधारणा
दिए गए N संख्याओं के संबंध में, लक्ष्य संख्याओं के न्यूनतम हटाने को निर्धारित करना है ताकि शेष संख्याओं का GCD N संख्याओं के प्रारंभिक GCD से बड़ा हो। यदि GCD को बढ़ाना असंभव है, तो "NO" प्रिंट करें।
उदाहरण
इनपुट
b[] = {1, 2, 4}
आउटपुट
1
पहला तत्व हटाने के बाद, नया GCD 2 है, जो प्रारंभिक GCD यानी 1 से बड़ा है।
इनपुट
b[] = {6, 9, 15, 30}
आउटपुट
3
प्रारंभिक gcd 3 है, 6 और 9 को हटाकर 15 का gcd प्राप्त करें जो 3 से बड़ा है। हम 9 और 15 को हटाकर 6 का gcd भी प्राप्त कर सकते हैं।
विधि
- यूक्लिडियन एल्गोरिदम का उपयोग करके N संख्याओं का gcd खोजें।
- सभी संख्याओं को निर्धारित gcd से विभाजित करें।
- कई क्वेरी के लिए अभाज्य गुणनखंड तकनीक का उपयोग करके, प्रत्येक संख्या का अभाज्य गुणनखंड O(log N) में निर्धारित करें।
- इस विधि से प्राप्त अभाज्य गुणनखंडों में डुप्लिकेट को खत्म करने के लिए सभी अभाज्य गुणनखंडों को सेट में डालें।
- हैश-मैप दृष्टिकोण का उपयोग करके, प्रत्येक i-वें तत्व में अभाज्य गुणनखंडों की आवृत्तियों की गणना करें।
- जब संख्याओं का गुणनखंड किया जा चुका हो, और गिनती आवृत्ति तालिका में संग्रहीत हो, तो हैश-मैप में पुनरावृति करें और उस अभाज्य गुणनखंड को ढूंढें जो सबसे अधिक बार आता है। यह अभाज्य गुणनखंड N नहीं हो सकता, क्योंकि हमने सरणी तत्वों को प्रारंभ में N संख्याओं के प्रारंभिक gcd से विभाजित किया है।
- परिणामस्वरूप, हटाने की संख्या हमेशा N-(hash[prime_factor]) होगी यदि प्रारंभिक gcd के विभाजन के बाद ऐसे कोई गुणनखंड हैं।
C++ कार्यान्वयन
// C++ program to find minimum removals so that gcd of remaining numbers is more than initial gcd
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
int spf1[MAXN];
void sieve1(){
spf1[1] = 1;
for (int i = 2; i < MAXN; i++)
spf1[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf1[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (spf1[i] == i) {
for (int j = i * i; j < MAXN; j += i)
if (spf1[j] == j)
spf1[j] = i;
}
}
}
vector<int> getFactorization1(int x){
vector<int> ret;
while (x != 1) {
ret.push_back(spf1[x]);
x = x / spf1[x];
}
return ret;
}
int minimumRemovals1(int a1[], int n){
int g = 0;
for (int i = 0; i < n; i++)
g = __gcd(a1[i], g);
unordered_map<int, int> mpp;
for (int i = 0; i < n; i++)
a1[i] = a1[i] / g;
for (int i = 0; i < n; i++) {
vector<int> p = getFactorization1(a1[i]);
set<int> s1;
for (int j = 0; j < p.size(); j++)
s1.insert(p[j]);
for (auto it = s1.begin(); it != s1.end(); it++) {
int el = *it;
mpp[el] += 1;
}
}
int mini = INT_MAX;
for (auto it = mpp.begin(); it != mpp.end(); it++) {
int fir1 = it->first;
int sec1 = it->second;
if ((n - sec1) <= mini)
mini = n - sec1;
}
if (mini != INT_MAX)
return mini;
else
return -1;
}
int main(){
int a1[] = { 6, 9, 15, 30 };
int n = sizeof(a1) / sizeof(a1[0]);
sieve1();
cout << minimumRemovals1(a1, n);
return 0;
}
आउटपुट
2