打印在C ++中至少彼此可整除的数组元素

Z时代
2024-01-10
分类：综合

在这个问题中，我们得到了一个整数数组，我们只需要打印那些可被数组中至少一个其他元素整除的数字。

让我们举个例子来更好地理解这个概念，

Input : 3 12 16 21

Output : 12 21

解释-3是最小的，因此可以被其他任何整数整除的数是：12被3整除，16被3整除，然后21被3整除。因此，我们将忽略3和16。

一种简单的方法是检查所有元素是否可以被数组的其他任何元素整除。但这不是解决该问题的最佳方法。

使用哈希可以是更好的解决方案。我们将数组的元素存储在哈希中，然后找到数组的max元素。然后，直到最大数量，最大元素将找到给定数量的倍数，如果在哈希中找到多个，则该元素将被数组中的至少一个元素除。这样，我们将打印除以数组中至少一个元素的元素。

示例

现在，基于此概念，我们可以创建一个程序-

#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;
}