এই বিভাগে আমরা আরেকটি আকর্ষণীয় সমস্যা দেখতে পাব। ধরুন আমাদের কাছে N উপাদানের একটি অ্যারে আছে। এই অ্যারেটিকে কো-প্রাইম অ্যারে হিসাবে তৈরি করতে আমাদের ন্যূনতম সংখ্যক ছেদ বিন্দু খুঁজে বের করতে হবে। কো-প্রাইম অ্যারেতে প্রতি দুটি পরপর উপাদানের 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