এই টিউটোরিয়ালটি একটি সমস্যা নিয়ে আলোচনা করবে যেখানে আমাদেরকে স্বতন্ত্র ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে। আমাদের সবচেয়ে বড় উপসেটটি খুঁজে বের করতে হবে যাতে প্রতিটি জোড়ার জন্য বড় উপাদান একটি ছোট উপাদান দ্বারা ভাগ করা হয়, উদাহরণস্বরূপ −
Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.
Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1 সমাধান খোঁজার পদ্ধতি
দুটি ভিন্ন পদ্ধতি রয়েছে যা আমরা এই টিউটোরিয়ালে ব্যাখ্যা করব।
সরল পদ্ধতি
একটি সহজ পদ্ধতিতে, আমরা এই সমস্যা সমাধানের জন্য পুনরাবৃত্তি প্রয়োগ করতে পারি। আমরা প্রতিটি উপাদান নেব এবং এটি উপসেটে অন্তর্ভুক্ত করা উচিত কিনা তা পরীক্ষা করব। ধরা যাক আমরা প্রথম উপাদান দিয়ে শুরু করি। আমাদের কাছে দুটি বিকল্প থাকবে, হয় উপসেটে অন্তর্ভুক্ত করা বা প্রথম উপাদানটির জন্য নয়। প্রথম উপাদান অন্তর্ভুক্ত করা যাক. তারপরে দ্বিতীয় উপাদানটিকে উপসেটে অন্তর্ভুক্ত করার জন্য, এটি সাবস্ট্রিং-এর উপাদানগুলি দ্বারা বিভাজ্য বা ভাগ করা উচিত, যেমন, প্রথম উপাদান। এইভাবে আমরা অ্যারে জুড়ে যাব। সুতরাং 2^n সম্ভাব্য পথ থাকবে যা O(2^n) এর সময় জটিলতা তৈরি করবে। আসুন এই সমস্যা সমাধানের সম্ভাব্য পদ্ধতির দিকে তাকাই।
দক্ষ পদ্ধতি
এই সমস্যায় ডাইনামিক প্রোগ্রামিং ব্যবহার করে একটি দক্ষ পন্থা প্রয়োগ করা যেতে পারে।
-
সঠিক উপাদান দ্বারা বিভাজ্য বাম উপাদান পেতে অ্যারে সাজান. আমাদের একবার বিভাজ্যতা পরীক্ষা করতে হবে।
-
ith সূচক পর্যন্ত সবচেয়ে বড় বিভাজ্য উপসেট সঞ্চয় করতে আমরা দীর্ঘতম ক্রমবর্ধমান সাবসেকুয়েন্স, অর্থাৎ আমাদের dp[ ] অ্যারে নেব। আমরা প্রতিটি সূচীকে একটি দিয়ে শুরু করব কারণ প্রতিটি উপাদান নিজেকে বিভক্ত করে।
-
এখন আমরা ২য় সূচক থেকে পুনরাবৃত্তি করব এবং বর্তমান সূচকের সাথে শেষ হওয়া সর্বাধিক বিভাজ্য উপসেটের জন্য প্রতিটি উপাদান পরীক্ষা করব। এইভাবে, আমরা প্রতিটি সূচকের জন্য সর্বাধিক উপসেট খুঁজে পাব।
-
এখন অ্যারের মাধ্যমে অতিক্রম করুন, এবং প্রতিটি উপাদানের জন্য, একটি ভাজক খুঁজুন যার বিভাজ্য গণনা সবচেয়ে বড়। এবং বর্তমান সূচকের বিভাজ্য গণনার মানকে সেই উপাদান + 1-এর বিভাজ্য গণনায় পরিবর্তন করুন।
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include<bits/stdc++.h>
using namespace std;
int main(){
int nums[] = {1, 2, 3, 6};
int n = sizeof(nums)/sizeof(int);
// sorting the array to exclude one condition for division.
sort(nums, nums+n);
vector <int> prev_res(n, -1);
// vector to store divisors of all the elements
vector <int> dp(n, 1);
int max = 1;
for (int i=1; i<n; i++){ // Check if there's a divisor of ith element present at jth index.
for (int j=0; j<i; j++){
if (nums[i]%nums[j] == 0){
// check If adding that increases the number of elements in subsequence.
if (dp[i] < dp[j] + 1){
dp[i] = dp[j]+1;
prev_res[i] = j;
}
}
}
// finding index having a maximum number of subsets.
if(max<dp[i])
max = dp[i];
}
cout << "Largest divisible subset in the array: ";
// printing the maximum subset
int k = max;
while (k >= 0){
cout << nums[k] << " ";
k = prev_res[k];
}
return 0;
} আউটপুট
Largest divisible subset in the array: 6 2 1
উপসংহার
এই টিউটোরিয়ালে, আমরা একটি সমস্যা নিয়ে আলোচনা করেছি:প্রদত্ত অ্যারেতে আমাদের সবচেয়ে বড় বিভাজ্য উপসেট খুঁজে বের করতে হবে যেখানে প্রতিটি জোড়ার পূর্ণসংখ্যা বিভাজ্য। আমরা পুনরাবৃত্তি থেকে একটি পদ্ধতি নিয়ে আলোচনা করেছি যা সূচকীয় সময় জটিলতা তৈরি করে, তাই আমরা একটি গতিশীল প্রোগ্রামিং সমাধান নিয়ে আলোচনা করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম নিয়েও আলোচনা করেছি যা আমরা সি, জাভা, পাইথন ইত্যাদি প্রোগ্রামিং ভাষার সাথে করতে পারি। আমরা আশা করি এই টিউটোরিয়ালটি আপনার কাজে লাগবে।
