इस सेक्शन में हम एक और दिलचस्प समस्या देखेंगे। मान लीजिए हमारे पास N एलिमेंट्स का एक ऐरे है। हमें इस ऐरे को को-प्राइम ऐरे बनाने के लिए न्यूनतम इंटरसेक्शन पॉइंट्स ढूंढने हैं। को-प्राइम ऐरे में हर दो लगातार एलिमेंट्स का gcd 1 होता है। हमें ऐरे भी प्रिंट करना है।
मान लीजिए हमारे पास {5, 10, 20} जैसे एलिमेंट्स हैं। यह को-प्राइम ऐरे नहीं है। अब 5, 10 और 10, 20 के बीच 1 इंसर्ट करके, यह को-प्राइम ऐरे बन जाएगा। तो ऐरे इस तरह होगा {5, 1, 10, 1, 20}
एल्गोरिदम
makeCoPrime(arr, n): begin count := 0 i को 1 से n तक की रेंज में, करें यदि arr[i] और arr[i-1] का gcd 1 नहीं है, तो count को 1 से बढ़ाएं done count वैल्यू प्रदर्शित करें arr का पहला एलिमेंट प्रदर्शित करें i को 1 से n तक की रेंज में, करें यदि arr[i] और arr[i-1] का gcd 1 नहीं है, तो 1 प्रदर्शित करें एलिमेंट arr[i] प्रदर्शित करें done end
उदाहरण
#include <iostream> #include <algorithm> using namespace std; int makeCoPrime(int arr[], int n){ int count = 0; for(int i = 1; i<n; i++){ if(__gcd(arr[i], arr[i - 1]) != 1){ count++; } } cout << "Number of intersection points: " << count << endl; cout << arr[0] << " "; for(int i = 1; i<n; i++){ if(__gcd(arr[i], arr[i - 1]) != 1){ cout << 1 << " "; } cout << arr[i] << " "; } } int main() { int A[] = {2, 7, 28}; int n = sizeof(A)/sizeof(A[0]); makeCoPrime(A, n); }आउटपुट
Number of intersection points: 1 2 7 1 28