समस्या कथन
एक पूर्णांक सरणी गिरफ्तारी को देखते हुए, कार्य सरणी के सभी तत्वों को हटाने के लिए आवश्यक न्यूनतम संख्या में संचालन को प्रिंट करना है। तत्व को हटाते समय निम्नलिखित प्रतिबंध लगाया जाता है -
-
सरणी से किसी भी तत्व को यादृच्छिक रूप से चुना जा सकता है और इसके द्वारा विभाज्य प्रत्येक तत्व को सरणी से हटाया जा सकता है
अगर गिरफ्तारी [] ={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