ধরুন আমাদের 1 থেকে N পূর্ণসংখ্যা রয়েছে৷ আমরা একটি সুন্দর বিন্যাসকে একটি অ্যারে হিসাবে সংজ্ঞায়িত করব যা এই এন সংখ্যাগুলি দ্বারা সম্পূর্ণরূপে নির্মিত হয় যদি এই অ্যারেতে ith অবস্থানের (1 <=i <=N) জন্য নিম্নলিখিতগুলির একটি সত্য হয় −
- ith অবস্থানে থাকা সংখ্যাটিকে i দ্বারা ভাগ করা যায়।
- i ith অবস্থানে সংখ্যা দ্বারা বিভাজ্য।
সুতরাং যদি ইনপুট 2 হয়, তবে ফলাফলটিও 2 হবে, যেমন প্রথম সুন্দর বিন্যাস [1,2]। এখানে ১ম অবস্থানে (i=1) সংখ্যা হল 1, এবং 1 হল i (i=1) দ্বারা বিভাজ্য। তারপর ২য় অবস্থানে (i=2) সংখ্যা হল 2, এবং 2 হল i (i=2) দ্বারা বিভাজ্য। দ্বিতীয় সুন্দর বিন্যাস হল [2, 1]:এখানে ১ম অবস্থানে (i=1) সংখ্যা হল 2, এবং 2 হল i (i=1) দ্বারা বিভাজ্য। তারপর ২য় অবস্থানে থাকা সংখ্যা (i=2) হল 1, এবং i (i=2) হল 1 দ্বারা বিভাজ্য৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন solve(), যা ভিজিট করা অ্যারে, এন্ড এবং pos নেবে। পোস প্রাথমিকভাবে 1।
- যদি pos =end + 1 হয়, তাহলে উত্তর 1 দ্বারা বাড়ান এবং ফেরত দিন
- আমি রেঞ্জ 1 থেকে শেষ পর্যন্ত
- i
- আমি ভিজিট করেছি হিসেবে চিহ্নিত করুন
- সমাধান (ভিজিট করা, শেষ, pos + 1)
- আমাকে দেখা হয়নি বলে চিহ্নিত করুন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int ans;
void solve(vector <bool>& visited, int end, int pos = 1){
if(pos == end + 1){
ans++;
return;
}
for(int i = 1; i <= end; i++){
if(!visited[i] && (pos % i == 0 || i % pos == 0)){
visited[i] = true;
solve(visited, end, pos + 1);
visited[i] = false;
}
}
}
int countArrangement(int N) {
ans = 0;
vector <bool> visited(N);
solve(visited, N);
return ans;
}
};
main(){
Solution ob;
cout << (ob.countArrangement(2));
} ইনপুট
2
আউটপুট
2
