C++ में दिए गए नियमों के साथ तत्वों को हटाकर ऐरे का न्यूनतम संभव आकार ढूंढना

इस समस्या में, हमें n संख्याओं का एक ऐरे और एक पूर्णांक मान k दिया गया है। हमारा कार्य दिए गए नियमों के साथ तत्वों को हटाकर ऐरे का न्यूनतम संभव आकार ढूंढना है।

समस्या विवरण - हमें ऐरे में तत्वों की संख्या को न्यूनतम करना है। निम्नलिखित डिलीशन ऑपरेशन का उपयोग करके, एक बार में हटाए जा सकने वाले तत्वों की संख्या 3 है। डिलीशन संभव है यदि तीन तत्व दो दी गई शर्तों को पूरा करते हैं,

शर्त 1 - तीन तत्व आसन्न होने चाहिए।

शर्त 2 - दो आसन्न तत्वों के बीच का अंतर 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 हो सकते हैं जो अब डिलीशन के लिए शर्त को पूरा करते हैं। इस प्रकार की समस्याएं जिनमें ओवरलैपिंग सबप्रॉब्लम्स होते हैं, डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करके हल की जा सकती हैं। इसके लिए, हम सबप्रॉब्लम्स के परिणामों को स्टोर करने के लिए एक DP[][] मैट्रिक्स बनाए रखेंगे ताकि आवश्यकता पड़ने पर बाद में उन्हें एक्सेस किया जा सके, इसे मेमोइज़ेशन कहा जाता है।

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

उदाहरण

#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 << "हटाने के बाद ऐरे का न्यूनतम संभव आकार है " << calcMinSize(arr, 0, n - 1, k);
   return 0;
}

आउटपुट

हटाने के बाद ऐरे का न्यूनतम संभव आकार है 3

एल्गोरिथ्म विश्लेषण

• समय जटिलता: O(n³) - तीन नेस्टेड लूप्स के कारण
• स्पेस जटिलता: O(n²) - DP टेबल के लिए
• दृष्टिकोण: इंटरवल DP के साथ मेमोइज़ेशन
• स्थिति: DP[l][r] = सबऐरे arr[l..r] का न्यूनतम आकार

मुख्य अवलोकन

डिलीशन के लिए तीन तत्वों को arithmetic progression बनाना होगा जिसमें कॉमन डिफरेंस k हो। डिलीशन के बाद, शेष भाग स्वतंत्र रूप से हल होते हैं।