मान लीजिए कि हमारे पास आकार N का एक सरणी है। इसमें N धनात्मक संख्याएँ हैं। हमें सभी संभावित उप-सरणी के न्यूनतम तत्वों को खोजना होगा। मान लीजिए कि सरणी {2, 66, 14, 521} है, तो न्यूनतम LCM 2 है, और GCD 1 है।
हम लालची दृष्टिकोण का उपयोग करके इस समस्या का समाधान करेंगे। यदि हम तत्वों की संख्या घटाते हैं, तो LCM कम होगा, और यदि हम सरणी का आकार बढ़ाते हैं, तो GCD कम होगा। हमें सरणी से सबसे छोटा तत्व खोजने की आवश्यकता है, जो कि एक एकल तत्व है, जिसे LCM की आवश्यकता होगी। जीसीडी के लिए, जीसीडी सरणी के सभी तत्वों का जीसीडी होगा।
उदाहरण
#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