ধারণা
প্রদত্ত 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 থেকে বড়।
পদ্ধতি
উপরের সমস্যাটি সমাধান করার জন্য আমাদের নিম্নলিখিত পদক্ষেপগুলি অনুসরণ করা উচিত -
-
প্রথমে আমাদের ইউক্লিডীয় অ্যালগরিদম প্রয়োগ করে N সংখ্যার gcd নির্ধারণ করা উচিত।
-
আমাদের সমস্ত সংখ্যাকে নির্ধারিত gcd দ্বারা ভাগ করা উচিত।
-
মাল্টিপল কোয়েরি টেকনিকের জন্য প্রাইম ফ্যাক্টরাইজেশন প্রয়োগ করে, আমাদের O(log N) এর প্রতিটি সংখ্যার প্রাইম ফ্যাক্টরাইজেশন নির্ধারণ করা উচিত।
-
এই পদ্ধতি প্রয়োগ করে প্রাপ্ত ডুপ্লিকেটগুলি দূর করার জন্য আমাদের সেটে সমস্ত প্রধান উপাদান সন্নিবেশ করতে হবে৷
-
একটি হ্যাশ-ম্যাপ পদ্ধতি প্রয়োগ করে, আমাদের প্রতিটি i-th উপাদানের প্রধান উপাদানগুলির ফ্রিকোয়েন্সি গণনা করা উচিত।
-
যে সময়ে সংখ্যার ফ্যাক্টরাইজেশন সঞ্চালিত হয়েছে, এবং গণনাগুলি ফ্রিকোয়েন্সি টেবিলে সংরক্ষণ করা হয়েছে, হ্যাশ-ম্যাপে পুনরাবৃত্তি করুন এবং প্রধান ফ্যাক্টর নির্ধারণ করুন যা সবচেয়ে বেশি বার ঘটে। এই মৌলিক ফ্যাক্টরটি N হতে পারে না, কারণ আমরা ইতিমধ্যেই অ্যারের উপাদানগুলিকে প্রাথমিকভাবে N সংখ্যার প্রাথমিক gcd দ্বারা ভাগ করেছি৷
-
ফলস্বরূপ, প্রাথমিক gcd বিভাজনের পরে যদি এই ধরনের কোনো কারণ থাকে তবে অপসারণের সংখ্যা সর্বদা N-(হ্যাশ[প্রাইম_ফ্যাক্টর]) হবে।
উদাহরণ
// 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
