Tuyên bố vấn đề
Cho một mảng số nguyên arr, nhiệm vụ là in ra số lượng phép toán tối thiểu cần thiết để xóa tất cả các phần tử của mảng. Trong khi việc xóa phần tử sau hạn chế được áp dụng -
-
Bất kỳ phần tử nào từ mảng có thể được chọn ngẫu nhiên và mọi phần tử chia hết cho nó đều có thể bị xóa khỏi mảng
Nếu arr [] ={2, 4, 15, 10, 8, 5, 3} thì cần 3 thao tác để xóa tất cả các phần tử -
- Nếu chúng tôi chọn 2 thì nó sẽ xóa {2, 4, 10, 8}
- Nếu chúng tôi chọn 5 thì nó sẽ xóa {5, 15}
- Nếu chúng tôi chọn 3 thì nó sẽ bị xóa {3}
Thuật toán
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
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Minimum required operations = 3