C++-এ N-এর চার গুণনীয়ক যাদের যোগফল N এবং গুণফল সর্বোচ্চ (সেট-২)

কনসেপ্ট

একই সমস্যা: N-এর চার গুণনীয়ক যাদের যোগফল N এবং গুণফল সর্বোচ্চ। এখানে O(P³) এর পরিবর্তে O(N²) পদ্ধতি ব্যাখ্যা করা হয়েছে (P = গুণনীয়কের সংখ্যা)।

ইনপুট

N = 60

আউটপুট

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625

১৫ চারবার বেছে নিলে: ১৫+১৫+১৫+১৫=৬০, গুণফল ৫০৬২৫।

পদ্ধতি (O(N²))

সব গুণনীয়ক ভেক্টরে রাখুন।
সব জোড়ার যোগফল (pair sum) অন্য কন্টেইনারে রাখুন এবং কোন জোড়া দিয়ে বানেছে সেটাও সংরক্ষণ করুন।
প্রতিটি pair_sum-এর জন্য N - pair_sum অন্য কন্টেইনারে আছে কিনা চেক করুন। থাকলে দুটি জোড়া মিলিয়ে চতুর্থক তৈরি হয়।
সর্বোচ্চ গুণফল वालাটি বেছে নিন।

উদাহরণ (C++ কোড)

// C++: O(N²) পদ্ধতিতে চার গুণনীয়ক
#include <bits/stdc++.h>
using namespace std;

void findfactors1(int q) {
    vector vec1;
    for (int i=1; i*i<=q; i++)
        if (q%i==0) { vec1.push_back(i); vec1.push_back(q/i); }
    sort(vec1.begin(), vec1.end());
    cout << "All the factors are -> ";
    for (int x:vec1) cout << x << " "; cout << endl;
    int maxProduct1=1; bool flag1=1;
    for (int i=0; i " << maxProduct1 << endl;
    else cout << "Not possible" << endl;
}

int main() { int q=60; findfactors1(q); return 0; }

আউটপুট

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625