समस्या कथन
एक सरणी "arr" दी गई है, सरणी को अच्छा बनाने के लिए हटाए जाने वाले न्यूनतम तत्वों की संख्या ढूंढें।
एक अनुक्रम a1, a2, a3...an को अच्छा कहा जाता है यदि प्रत्येक तत्व a[i] के लिए, एक तत्व a[j] (i ≠ j) मौजूद होता है जैसे कि a[i] + a[j] 2 की घात हो।
arr1[] = {1, 1, 7, 1, 5}
उपरोक्त सरणी में यदि हम तत्व '5' को हटा दें तो सरणी अच्छी सरणी बन जाती है। इसके बाद arr[i] + arr[j] का कोई भी जोड़ा 2 की घात होता है:
- arr[0] + arr[1] = (1 + 1) = 2 जो 2 की घात है
- arr[0] + arr[2] = (1 + 7) = 8 जो 2 की घात है
एल्गोरिदम
1. हमें केवल ऐसे a[i] को हटाना है जिनके लिए कोई a[j] नहीं है जैसे कि a[i] + a[j] 2 की घात है। 2. प्रत्येक मान की सरणी में घटनाओं की संख्या ढूंढें 3. जांचें कि a[i] का कोई जोड़ा a[j] नहीं है
C++ उदाहरण
#include <iostream>
#include <map>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minDeleteRequred(int *arr, int n) {
map<int, int> frequency;
for (int i = 0; i < n; ++i) frequency[arr[i]]++;
int delCnt = 0;
for (int i = 0; i < n; ++i) {
bool doNotRemove = false;
for (int j = 0; j < 31; ++j) {
int pair = (1 << j) - arr[i];
if (frequency.count(pair) &&
(frequency[pair] > 1 || (frequency[pair] == 1 && pair != arr[i]))) {
doNotRemove = true;
break;
}
}
if (!doNotRemove) ++delCnt;
}
return delCnt;
}
int main() {
int arr[] = {1, 1, 7, 1, 5};
cout << "Minimum elements to be deleted = " << minDeleteRequred(arr, SIZE(arr)) << endl;
return 0;
}
आउटपुट
Minimum elements to be deleted = 1