समस्या कथन
एक सरणी "गिरफ्तारी" को देखते हुए, कार्य सरणी को अच्छा बनाने के लिए हटाए जाने वाले तत्वों की न्यूनतम संख्या को खोजना है।
अनुक्रम a1, a2, a3. . .an को अच्छा कहा जाता है यदि प्रत्येक तत्व a[i] के लिए एक तत्व a[j] (i के बराबर नहीं है) मौजूद है जैसे कि a[i] + a[j] दो की शक्ति है।
arr1[] = {1, 1, 7, 1, 5} उपरोक्त सरणी में यदि हम तत्व '5' हटाते हैं तो सरणी अच्छी सरणी बन जाती है। इसके बाद arr[i] + arr[j] का कोई भी जोड़ा दो की घात है -
- arr[0] + arr[1] =(1 + 1) =2 दो में से कौन सा घात
- arr[0] + arr[2] =(1 + 7) =8 जो दो की शक्ति है
एल्गोरिदम
1. We have to delete only such a[i] for which there is no a[j] such that a[i] + a[i] is a power of 2. 2. For each value find the number of its occurrences in the array 3. Check that a[i] doesn’t have a pair a[j]
उदाहरण
#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