Trong bài toán này, chúng ta được cung cấp một mảng các số nguyên và chúng ta chỉ phải in những số đó chia hết cho ít nhất một phần tử khác của mảng.
Hãy lấy một ví dụ để hiểu rõ hơn về khái niệm này,
Input : 3 12 16 21 Output : 12 21
Giải thích - 3 là số nhỏ nhất nên có thể chia hết cho bất kỳ số nào khác là 12 chia hết cho 3, 16 không chia hết cho 3 và 21 chia hết cho 3. Vì vậy, chúng ta sẽ bỏ qua 3 và 16.
Một cách dễ dàng là kiểm tra xem tất cả các phần tử có chia hết cho bất kỳ phần tử nào khác của mảng hay không. Nhưng đây không phải là giải pháp tốt nhất có thể cho vấn đề.
Sử dụng hàm băm có thể là một giải pháp tốt hơn. Chúng tôi sẽ lưu trữ các phần tử của một mảng trong hàm băm và sau đó tìm phần tử tối đa của mảng. Và sau đó, các phần tử tối đa này tìm bội số của một số nhất định và nếu bội số được tìm thấy trong hàm băm thì phần tử đó được chia cho ít nhất một phần tử của mảng. Như vậy, chúng tôi sẽ in phần tử được chia cho ít nhất một phần tử của mảng.
Ví dụ
Bây giờ, dựa trên khái niệm này, hãy tạo một chương trình -
#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;
} Đầu ra
12 14 4