C++-এ অ্যারে এর অধিকাংশ এলিমেন্টকে ভাগ করে এমন পূর্ণসংখ্যা বের করুন

একটি ইন্টিজার অ্যারে দেওয়া আছে। এমন একটি পূর্ণসংখ্যা p খুঁজতে হবে যেটি অ্যারের সর্বোচ্চ সংখ্যক এলিমেন্টকে ভাগ করে। একাধিক হলে ছোটটি রিটার্ন করুন।

উদাহরণ

ইনপুট: arr = {4,5,6,7,8}

2 ভাগ করে: {4,6,8} (৩টি) → আউটপুট: 2

অ্যালগরিদম ১: ব্রুট-ফোর্স (O(n×maxVal))

প্রতিটি এলিমেন্টের সব dzielন চেক করুন। ধীর।

অ্যালগরিদম ২: প্রাইম ফ্যাক্টর ফিকোয়েন্সি (O(n log maxVal))

1. Sieve of Eratosthenes দিয়ে সব সংখ্যার স্মলেস্ট প্রাইম ফ্যাক্টর (SPF) প্রीकম্পিউট করুন।
2. প্রতিটি অ্যারে এলিমেন্টকে SPF দিয়ে ফ্যাক্টরাইজ করুন, ইউনিক প্রাইম ফ্যাক্টরগুলোর ফ্রিকোয়েন্সি বড়ান।
3. সর্বোচ্চ ফ্রিকোয়েন্সি वाले প্রাইমটি উত্তর (টাই ব্রেক: ছোট প্রাইম)।

কারণ: যেকোনো কম্পোজিট dzielনও তার প্রাইম ফ্যাক্টরদ্বারা বিভাজ্য। প্রাইম ফ্যাক্টর ফ্রিকোয়েন্সি চেক করলেই কম্পোজিটের ফ্রিকোয়েন্সি বুঝা যায়।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001

int spf[MAXN]; // Smallest Prime Factor

void findPrimeSieve() {
    spf[1] = 1;
    for (int i = 2; i < MAXN; i++) spf[i] = i;
    for (int i = 4; i < MAXN; i += 2) spf[i] = 2;
    for (int i = 3; i * i < MAXN; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j < MAXN; j += i)
                if (spf[j] == j) spf[j] = i;
        }
    }
}

vector findFactors(int num) {
    vector factors;
    while (num != 1) {
        int temp = spf[num];
        factors.push_back(temp);
        while (num % temp == 0) num /= temp;
    }
    return factors;
}

int findMaxDivElement(int arr[], int n) {
    findPrimeSieve();
    map factorFreq;
    for (int i = 0; i < n; ++i) {
        vector p = findFactors(arr[i]);
        for (int f : p) factorFreq[f]++;
    }
    int cnt = 0, ans = 1e7;
    for (auto itr : factorFreq) {
        if (itr.second >= cnt) {
            cnt = itr.second;
            ans = min(ans, itr.first);
        }
    }
    return ans;
}

int main() {
    int arr[] = {4,5,6,7,8};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "The number that divides the maximum elements of the array is " << findMaxDivElement(arr, n);
    return 0;
}

আউটপুট

The number that divides the maximum elements of the array is 2

ব্যাখ্যা

• spf অ্যারে প্রতিটি সংখ্যার সবচেয়ে ছোট প্রাইম ফ্যাক্টর রাখে।
• findFactors SPF ব্যবহার করে O(log n)-এ প্রাইম ফ্যাক্টরাইজেশন করে।
• map (বিএসটি) দিয়ে ফ্রিকোয়েন্সি কাউন্ট — অটোমেটিক সোর্টেড (ছোট প্রাইম আগে) আমি অটোমেটিক হ্যান্ডেল হয়।
• টাইম: O(MAXN log log MAXN + n log maxVal)।

নোট

যদি কম্পোজিট dzielন (যেমন ৪, ৬) চাই, তবে সব dzielন এনুমারেট করতে হবে। প্রাইম ফ্যাক্টর পদ্ধতি শুধু প্রাইম делиমিটার খুঁজে।