আমাদের পূর্ণসংখ্যা উপাদানগুলির একটি অ্যারে দেওয়া হয়েছে এবং কাজটি হল প্রদত্ত অ্যারে থেকে সাব-সিকুয়েন্সগুলি খুঁজে বের করা যার মধ্যে 1 হিসাবে GCD রয়েছে৷ GCD হল দুই বা ততোধিকের সর্বশ্রেষ্ঠ সাধারণ ভাজক। পূর্ণসংখ্যা যা প্রদত্ত সংখ্যাগুলিকে সম্পূর্ণভাবে ভাগ করে এবং সবার মধ্যে সর্বশ্রেষ্ঠ।
ইনপুট − int arr[] ={3, 4, 8, 16}
আউটপুট − GCD 1 সহ সাব-সিকুয়েন্সের সংখ্যা হল − 7
ব্যাখ্যা −
1 হিসাবে GCD দিয়ে প্রদত্ত অ্যারে থেকে যে সাব-সিকুয়েন্সগুলি তৈরি করা যেতে পারে তা হল (3, 4), (3, 8), (3, 16), (4, 3), (8, 3), (16, 3), (3, 4, 8)
ইনপুট − int arr[] ={5, 7, 10}
আউটপুট − GCD 1 সহ সাব-সিকুয়েন্সের সংখ্যা হল − 3
ব্যাখ্যা −
1 হিসাবে GCD দিয়ে প্রদত্ত অ্যারে থেকে যে সাব-সিকুয়েন্সগুলি তৈরি করা যেতে পারে তা হল (5, 7), (7, 10), (5, 7, 10)
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
প্রদত্ত আকারের পূর্ণসংখ্যা উপাদানগুলির একটি অ্যারে ইনপুট করুন৷
-
একটি অ্যারের আকার গণনা করুন এবং আরও প্রক্রিয়াকরণের জন্য ফাংশনে ডেটা পাস করুন
-
GCD সহ সাব-সিকোয়েন্সের গণনা 1 হিসাবে সংরক্ষণ করতে একটি অস্থায়ী পরিবর্তনশীল গণনা ঘোষণা করুন
-
একটি অ্যারের আকার পর্যন্ত i থেকে 0 পর্যন্ত লুপ শুরু করুন
-
লুপের ভিতরে j থেকে 0 পর্যন্ত একটি অ্যারের আকার পর্যন্ত FOR আর একটি লুপ শুরু করুন
-
লুপের ভিতরে, IF GCD(arr[i], arr[j]) =TRUE চেক করুন তারপর গণনা 1 দ্বারা বৃদ্ধি করুন
-
রিটার্ন গণনা
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
# include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if (a == 0)
return b;
return gcd(b % a, a);
}
int GCD_1(int arr[],int size){
int count = 0;
for(int i=0;i<size;i++){
for(int j=0;j<=size;j++){
if(gcd(arr[i],arr[j])==1){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {3, 4, 8, 16};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of sub-sequences with GCD 1 are: "<<GCD_1(arr, size);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of number of sub-sequences with GCD 1 are: 7
