इस समस्या में, हमें n संख्याओं की एक सरणी और एक पूर्णांक मान k दिया जाता है। हमारा कार्य तत्वों को हटाने के लिए दिए गए नियमों के साथ सरणी का न्यूनतम संभव आकार खोजना है।
समस्या का विवरण - हमें सरणी में तत्वों की संख्या को कम करने की आवश्यकता है। फॉलो डिलीट ऑपरेशन का उपयोग करके, एक बार में हटाए जा सकने वाले तत्वों की संख्या 3 है। यदि तीन तत्व दो दी गई शर्तों को पूरा करते हैं, तो हटाना संभव है,
शर्त 1 − तीन तत्व आसन्न होने चाहिए।>
दूसरी शर्त - पास के दो तत्वों के बीच का अंतर k है, यानी arr[i + 1] =arr[i] + k और arr[i+2] =arr[i+1] + k.
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
{4, 6, 8, 4, 1, 5 }, k = 2 आउटपुट
3
स्पष्टीकरण
इंडेक्स 0, 1, 2 के लिए एक डिलीट ऑपरेशन संभव है।
समाधान दृष्टिकोण
इस समस्या को हल करना थोड़ा मुश्किल है क्योंकि अप्रत्यक्ष विलोपन संचालन संभव हो सकता है जिसे एक विलोपन ऑपरेशन के बाद देखा जा सकता है। उदाहरण के लिए, हम 5, 6, 7 पर तत्वों को हटाते हैं। इस विलोपन के बाद, नई सरणी में 3, 4, 5 तत्व हो सकते हैं जो अब हटाने की शर्त को पूरा करते हैं। इस तरह की समस्याएं जिनमें अतिव्यापी उपसमस्याएं हैं, एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करके हल किया जा सकता है। इसके लिए, हम उप-समस्याओं के परिणामों को संग्रहीत करने के लिए एक डीपी [] मैट्रिक्स बनाए रखेंगे, जब आवश्यक हो तो उन्हें बाद में एक्सेस करने के लिए, इसे मेमोरिज़ेशन कहा जाता है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k){
if (DP[start][end] != -1)
return DP[start][end];
if ( (end-start + 1) < 3)
return end-start +1;
int minSize = 1 + calcMinSize(arr, start+1, end, k);
for (int i = start+1; i<=end-1; i++){
for (int j = i+1; j <= end; j++ ){
if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] +
2*k) && calcMinSize(arr, start+1, i-1, k) == 0 && calcMinSize(arr, i+1, j- 1, k) == 0) {
minSize = min(minSize, calcMinSize(arr, j+1, end, k));
}
}
}
return (DP[start][end] = minSize);
}
int main() {
int arr[] = {4, 6, 8, 4, 1, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
memset(DP, -1, sizeof(DP));
cout<<"The minimum possible size of the array after removal is "<<calcMinSize(arr, 0, n-1, k);
return 0;
} आउटपुट
The minimum possible size of the array after removal is 3