इस समस्या में, हमें पूर्णांकों की एक सरणी दी जाती है और हमें केवल उन्हीं संख्याओं को मुद्रित करना होता है जो सरणी के कम से कम एक अन्य तत्व से विभाज्य हों।
आइए अवधारणा को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं,
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