C++ में सभी संभावित सब-एरेज में न्यूनतम LCM और GCD

मान लीजिए हमारे पास आकार N की एक सरणी arr है। इसमें N धनात्मक संख्याएं हैं। हमें सभी संभावित सबएरेज के न्यूनतम एलिमेंट्स ढूंढने हैं। मान लीजिए सरणी {2, 66, 14, 521} है, तो न्यूनतम LCM 2 है, और GCD 1 है।

हम इस समस्या को लालची दृष्टिकोण का उपयोग करके हल करेंगे। यदि हम एलिमेंट्स की संख्या घटाते हैं, तो LCM कम होगा, और यदि हम सरणी का आकार बढ़ाते हैं, तो GCD कम होगा। हमें सरणी से सबसे छोटा एलिमेंट ढूंढना होगा, जो एक एकल एलिमेंट है, वही आवश्यक LCM होगा। GCD के लिए, GCD सरणी के सभी एलिमेंट्स का GCD होगा।

उदाहरण

#include <iostream> #include <algorithm> using namespace std; int minimum_gcd(int arr[], int n) {    int GCD = 0;    for (int i = 0; i < n; i++)    GCD = __gcd(GCD, arr[i]);    return GCD; } int minimum_lcm(int arr[], int n) {    int LCM = arr[0];    for (int i = 1; i < n; i++)    LCM = min(LCM, arr[i]);    return LCM; } int main() {    int arr[] = { 2, 66, 14, 521 };    int n = sizeof(arr) / sizeof(arr[0]);    cout << "LCM: " << minimum_lcm(arr, n) << ", GCD: " << minimum_gcd(arr, n); }

आउटपुट

LCM: 2, GCD: 1