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