使用C ++删除数组的所有元素所需的最小操作数。

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

问题陈述

给定一个整数数组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;
}