C++を使用して配列のすべての要素を削除するために必要な操作の最小数。

問題の説明

整数配列arrが与えられた場合、タスクは、配列のすべての要素を削除するために必要な最小数の操作を出力することです。制限に続いて要素を削除している間-

• 配列から任意の要素をランダムに選択でき、それで割り切れるすべての要素を配列から削除できます

arr [] ={2、4、15、10、8、5、3}の場合、すべての要素を削除するには3つの操作が必要です-

• 2を選択すると、{2、4、10、8}が削除されます
• 5を選択すると、{5、15}が削除されます
• 3を選択すると、{3}
が削除されます

アルゴリズム

1. Sort the array in ascending order and count number occurrence of each element
2. For each unmarked element starting from beginning mark all elements which are divisible by choose element, and increase the result counter

例

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define MAX 100
using namespace std;
int getMinOperations(int *arr, int n){
   int map[MAX] = {0};
   sort(arr, arr + n);
   for (int i = 0; i < n; ++i) {
      map[arr[i]]++;
   }
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (map[arr[i]]) {
         for (int j = i; j < n; ++j) {
            if (arr[j] % arr[i] == 0) {
               map[arr[j]] = 0;
            }
         }
         ++cnt;
      }
   }
   return cnt;
}
int main(){
   int arr[] = {2, 4, 15, 10, 8, 5, 3};
   cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum required operations = 3