এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে এবং আমাদের শুধুমাত্র সেই সংখ্যাগুলিকে প্রিন্ট করতে হবে যেগুলি অ্যারের অন্তত একটি অন্য উপাদান দ্বারা বিভাজ্য৷
ধারণাটি আরও ভালভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : 3 12 16 21 Output : 12 21
ব্যাখ্যা − 3 হল সবচেয়ে ছোট তাই এটি অন্য যেকোনো সংখ্যা দ্বারা বিভাজ্য হতে পারে 12 যেটি 3 দ্বারা বিভাজ্য, 16টি 3 দ্বারা বিভাজ্য নয় এবং তারপর 21 যা 3 দ্বারা বিভাজ্য৷ সুতরাং, আমরা 3 এবং 16 কে অবহেলা করব৷
একটি সহজ উপায় হল সমস্ত উপাদানগুলি অ্যারের অন্য কোনও উপাদান দ্বারা বিভাজ্য কিনা তা পরীক্ষা করা। কিন্তু এটি সমস্যার জন্য সর্বোত্তম সম্ভাব্য সমাধান নয়৷
৷হ্যাশ ব্যবহার করে একটি ভাল সমাধান হতে পারে। আমরা হ্যাশে একটি অ্যারের উপাদান সংরক্ষণ করব এবং তারপর অ্যারের সর্বাধিক উপাদান খুঁজে বের করব। এবং তারপর এই সর্বাধিক উপাদানগুলি একটি প্রদত্ত সংখ্যার গুণিতক খুঁজে বের করে এবং যদি হ্যাশে একাধিক পাওয়া যায় তবে উপাদানটিকে অ্যারের অন্তত একটি উপাদান দ্বারা ভাগ করা হয়। এইভাবে, আমরা অ্যারের অন্তত একটি উপাদান দ্বারা বিভক্ত উপাদানটিকে প্রিন্ট করব৷
উদাহরণ
এখন, এই ধারণার উপর ভিত্তি করে একটি প্রোগ্রাম তৈরি করা যাক -
#include <bits/stdc++.h>
using namespace std;
void printDivisibleNumber(int arr[], int n){
unordered_set<int> s;
int maxElement = INT_MIN;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
maxElement = max(maxElement, arr[i]);
}
unordered_set<int> res;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
for (int j = arr[i] * 2; j <= maxElement; j += arr[i]) {
if (s.find(j) != s.end())
res.insert(j);
}
}
}
unordered_map<int, int> mp;
for (int i = 0; i <n; i++)
mp[arr[i]]++;
unordered_map<int, int>::iterator it;
vector<int> ans;
for (it = mp.begin(); it != mp.end(); it++) {
if (it->second >= 2) {
if (res.find(it->first) == res.end()) {
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
if (res.find(it->first) != res.end()) {
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
for (auto x : ans)
cout<<x<<"\t";
}
int main(){
int arr[] = {2, 4, 7 , 12 , 14 };
int n = sizeof(arr) / sizeof(arr[0]);
printDivisibleNumber(arr, n);
return 0;
} আউটপুট
12 14 4
