इस समस्या में, हमें आकार n की एक सरणी arr[] और एक संख्या S दी गई है। हमारा कार्य संशोधित सरणी के न्यूनतम मान का अधिकतम संभावित मान ज्ञात करना है।
यहां, सरणी को संशोधित करने के नियम हैं,
संशोधन से पहले और बाद में सरणी तत्वों के योग का अंतर S होना चाहिए।
संशोधित सरणी में ऋणात्मक मान अनुमत नहीं हैं।
यदि संशोधित सरणी में, सरणी के न्यूनतम मान को अधिकतम करने की आवश्यकता है।
सरणी का संशोधन सरणी के किसी भी तत्व को बढ़ाकर या घटाकर किया जा सकता है।
इन प्रतिबंधों का उपयोग करके, हमें नई सरणी ढूंढनी है और सरणी के सबसे छोटे तत्व के लिए अधिकतम मान लौटाना है।
उदाहरण से समझते हैं:
इनपुट: arr[] = {4, 5, 6} S = 2 आउटपुट: 4 व्याख्या
संशोधित सरणी है {4, 5, 5}
समाधान दृष्टिकोण
हमें संशोधित सरणी के सबसे छोटे मान को अधिकतम करना है। हम इसे बाइनरी सर्च का उपयोग करके न्यूनतम मान के लिए इष्टतम मान ढूंढकर करेंगे जो 0 (सबसे छोटा संभव) और arrmin (सबसे बड़ा संभव) के बीच है। हम सबसे छोटे संभव मान के लिए अंतर की जांच करेंगे।
कुछ विशेष शर्तें,
यदि S सरणी योग से अधिक है, तो कोई समाधान संभव नहीं है।
यदि S सरणी योग के बराबर है, तो 0 न्यूनतम तत्व का मान होगा।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include <iostream> using namespace std; int findmaximisedMin(int a[], int n, int S){ int minVal = a[0]; int arrSum = a[0]; for (int i = 1; i < n; i++) { arrSum += a[i]; minVal = min(a[i], minVal); } if (arrSum < S) return -1; if (arrSum == S) return 0; int s = 0; int e = minVal; int ans; while (s <= e) { int mid = (s + e) / 2; if (arrSum - (mid * n) >= S) { ans = mid; s = mid + 1; } else e = mid - 1; } return ans; } int main(){ int a[] = { 4, 5, 6 }; int S = 2; int n = sizeof(a) / sizeof(a[0]); cout<<"The maximum value of minimum element of the modified array is "<<findmaximisedMin(a, n, S); return 0; } आउटपुट
The maximum value of minimum element of the modified array is 4