समस्या कथन
एक पूर्णांक सरणी arr दी गई है, सरणी के सभी तत्वों को हटाने के लिए आवश्यक न्यूनतम ऑपरेशन की संख्या प्रिंट करें। तत्व हटाते समय निम्न प्रतिबंध है:
- सरणी से किसी भी तत्व को यादृच्छिक रूप से चुना जा सकता है और उससे विभाज्य हर तत्व को सरणी से हटाया जा सकता है
यदि arr[] = {2, 4, 15, 10, 8, 5, 3}, तो सभी तत्वों को हटाने के लिए 3 ऑपरेशन आवश्यक हैं:
- यदि हम 2 चुनते हैं तो यह {2, 4, 10, 8} हटा देगा
- यदि हम 5 चुनते हैं तो यह {5, 15} हटा देगा
- यदि हम 3 चुनते हैं तो यह {3} हटा देगा
एल्गोरिदम
1. सरणी को आरोही क्रम में सॉर्ट करें और प्रत्येक तत्व की घटनाओं को गिनें 2. शुरुआत से प्रत्येक अनमार्क्ड तत्व के लिए, चुने गए तत्व से विभाज्य सभी तत्वों को मार्क करें, और परिणाम काउंटर बढ़ाएं
C++ उदाहरण
#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