C++ में को-प्राइम ऐरे बनाने के लिए न्यूनतम इंसर्शन

इस खंड में हम एक और दिलचस्प समस्या देखेंगे। मान लीजिए कि हमारे पास एन तत्वों की एक सरणी है। इस सरणी को सह-अभाज्य सरणी बनाने के लिए हमें न्यूनतम संख्या में प्रतिच्छेदन बिंदु खोजने होंगे। को-प्राइम एरे में हर दो लगातार एलीमेंट का gcd 1 होता है। हमें ऐरे को भी प्रिंट करना होता है।

मान लीजिए हमारे पास {5, 10, 20} जैसे तत्व हैं। यह सह-प्रमुख सरणी नहीं है। अब 5, 10 और 10, 20 के बीच 1 डालने से यह को-प्राइम एरे होगा। तो ऐरे {5, 1, 10, 1, 20}

एल्गोरिदम

makeCoPrime(arr, n):
begin
   count := 0
   for i in range 1 to n, do
      if gcd of arr[i] and arr[i – 1] is not 1, then increase count by 1
   done
   display count value
   display the first element of arr
   for i in range 1 to n, do
      if gcd of arr[i] and arr[i – 1] is not 1, then display 1
   display element 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]) != i){
         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]) != i){
         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