समस्या कथन
N पूर्णांक और K दिए गए हैं, उन तत्वों की न्यूनतम संख्या ज्ञात करें जिन्हें हटाया जाना चाहिए ताकि Amax - Amin <= K। तत्वों को हटाने के बाद, Amax और Amin को शेष तत्वों में से माना जाता है
उदाहरण
यदि arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20} और k = 4 तो आउटपुट 5 होगा:
- सरणी की शुरुआत से 1, 3 और 4 हटाएं
- सरणी के अंत से 17 और 20 हटाएं
- अंतिम सरणी {9, 10, 11, 12} बन जाती है जहां 12 - 9 <= 4
एल्गोरिदम
1. दिए गए तत्वों को क्रमबद्ध करें 2. लालची दृष्टिकोण का उपयोग करके, सबसे अच्छा तरीका है न्यूनतम तत्व या अधिकतम तत्व को हटाना और फिर जांचना कि क्या Amax - Amin <= K। हटाने के विभिन्न संयोजनों पर विचार किया जाना है। 3. हटाने के दो संभावित तरीके होंगे, या तो हम न्यूनतम को हटाते हैं या हम अधिकतम को हटाते हैं। मान लें (i...j) हटाने के बाद बचे तत्वों के इंडेक्स हैं। प्रारंभ में, हम i=0 और j=n-1 से शुरू करते हैं और शुरुआत में हटाए गए तत्वों की संख्या 0 होती है। 4. हम केवल तभी तत्व हटाते हैं जब a[j]-a[i]>k, हटाने के दो संभावित तरीके हैं (i+1...j) या (i...j-1)। दोनों में से न्यूनतम माना जाता है
उदाहरण
#include <bits/stdc++.h> #define MAX 100 using namespace std; int dp[MAX][MAX]; int removeCombinations(int *arr, int i, int j, int k) { if (i >= j) { return 0; } else if ((arr[j] - arr[i]) <= k) { return 0; } else if (dp[i][j] != -1) { return dp[i][j]; } else if ((arr[j] - arr[i]) > k) { dp[i][j] = 1 + min(removeCombinations(arr, i + 1, j, k), removeCombinations(arr, i, j - 1,k)); } return dp[i][j]; } int removeNumbers(int *arr, int n, int k){ sort(arr, arr + n); memset(dp, -1, sizeof(dp)); return n == 1 ? 0 : removeCombinations(arr, 0, n - 1,k); } int main() { int arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20}; int n = sizeof(arr) / sizeof(arr[0]); int k = 4; cout << "हटाई जाने वाली न्यूनतम संख्या = " << removeNumbers(arr, n, k) << endl; return 0; }जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है
आउटपुट
हटाई जाने वाली न्यूनतम संख्या = 5
