ধারণা
একটি প্রদত্ত পূর্ণসংখ্যা N এর সাপেক্ষে, আমাদের কাজ হল N-এর সমস্ত গুণনীয়ক নির্ধারণ করা এবং N-এর গুণনীয়কগুলিকে মুদ্রণ করা যাতে −
- চারটি গুণনীয়কের যোগফল N এর সমান।
- চারটি কারণের গুণফল সবচেয়ে বড়।
এটা দেখা গেছে যে যদি এই ধরনের 4টি ফ্যাক্টর নির্ধারণ করা অসম্ভব হয় তবে "সম্ভব নয়" প্রিন্ট করুন। এটা লক্ষ করা উচিত যে পণ্যটিকে সর্বাধিক করার জন্য চারটি কারণ একে অপরের সমান হতে পারে।
ইনপুট
N = 60
আউটপুট
All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625
15 গুণনীয়কটি চারবার নির্বাচন করুন,
অতএব, 15+15+15+15 =60 এবং পণ্য সবচেয়ে বড়।
পদ্ধতি
এখানে একটি পদ্ধতি যা O(P^3) এর জটিলতা নেয়, যেখানে P হল N এর গুণনীয়ক সংখ্যা ব্যাখ্যা করা হয়েছে।
তাই সময় জটিলতার একটি কার্যকর পদ্ধতি O(N^2) নিম্নলিখিত পদক্ষেপগুলির সাহায্যে পাওয়া যেতে পারে।
- আমরা প্রদত্ত সংখ্যার সমস্ত গুণনীয়ক একটি পাত্রে সংরক্ষণ করি।
- এখন আমরা সমস্ত জোড়ার জন্য পুনরাবৃত্তি করি এবং তাদের যোগফল একটি ভিন্ন পাত্রে সংরক্ষণ করি।
- যে উপাদানগুলির দ্বারা যোগফল প্রাপ্ত হয়েছিল তা পেতে আমাদের সূচকটি (উপাদান 1 + উপাদান2) জোড়া (উপাদান1, উপাদান2) দিয়ে চিহ্নিত করতে হবে।
- আবার আমরা সমস্ত pair_sum-এর জন্য পুনরাবৃত্তি করি, এবং n-pair_sum একই পাত্রে বিদ্যমান কিনা তা যাচাই করি, ফলস্বরূপ উভয় জোড়াই চতুর্গুণ গঠন করে।
- যে উপাদানগুলির দ্বারা জুটি গঠিত হয়েছিল তা পেতে জোড়া হ্যাশ অ্যারে প্রয়োগ করুন৷
- অবশেষে, এই ধরনের চতুষ্পদগুলির মধ্যে সবচেয়ে বড়টি সংরক্ষণ করুন এবং শেষে এটি মুদ্রণ করুন।
উদাহরণ
// C++ program to find four factors of N
// with maximum product and sum equal to N
#include <bits/stdc++.h>
using namespace std;
// Shows function to find factors
// and to print those four factors
void findfactors1(int q){
vector<int> vec1;
// Now inserting all the factors in a vector s
for (int i = 1; i * i <= q; i++) {
if (q % i == 0) {
vec1.push_back(i);
vec1.push_back(q / i);
}
}
// Used to sort the vector
sort(vec1.begin(), vec1.end());
// Used to print all the factors
cout << "All the factors are -> ";
for (int i = 0; i < vec1.size(); i++)
cout << vec1[i] << " ";
cout << endl;
// So any elements is divisible by 1
int maxProduct1 = 1;
bool flag1 = 1;
// implementing three loop we'll find
// the three largest factors
for (int i = 0; i < vec1.size(); i++) {
for (int j = i; j < vec1.size(); j++) {
for (int k = j; k < vec1.size(); k++) {
// Now storing the fourth factor in y
int y = q - vec1[i] - vec1[j] - vec1[k];
// It has been seen that if the fouth factor become negative
// then break
if (y <= 0)
break;
// So we will replace more optimum number
// than the previous one
if (q % y == 0) {
flag1 = 0;
maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] *y,maxProduct1);
}
}
}
}
// Used to print the product if the numbers exist
if (flag1 == 0)
cout << "Product is -> " << maxProduct1 << endl;
else
cout << "Not possible" << endl;
}
// Driver code
int main(){
int q;
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
