C++で少なくとも互いに割り切れる配列要素を出力します

この問題では、整数の配列が与えられ、配列の他の少なくとも1つの要素で割り切れる数だけを出力する必要があります。

概念をよりよく理解するために例を見てみましょう。

Input  : 3 12 16 21
Output : 12 21

説明 − 3は最小であるため、他の数値で割り切れる可能性があります。12は3で割り切れ、16は3で割り切れず、21は3で割り切れます。したがって、3と16は無視します。

簡単な方法の1つは、すべての要素が配列の他の要素で割り切れるかどうかを確認することです。しかし、これは問題に対する最善の解決策ではありません。

ハッシュの使用 より良い解決策になる可能性があります。配列の要素をハッシュに格納してから、配列の最大要素を見つけます。そして、この最大要素までは、指定された数の倍数を検出し、ハッシュで複数が検出された場合、要素は配列の少なくとも1つの要素で除算されます。このように、配列の少なくとも1つの要素で分割された要素を出力します。

例

さて、このコンセプトに基づいてプログラムを作成しましょう-

#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