इस समस्या में, हमें आकार n और संख्या S का एक सरणी arr[] दिया जाता है। हमारा कार्य संशोधित सरणी के न्यूनतम मान का अधिकतम संभव मान ज्ञात करना है ।
यहाँ, सरणी को संशोधित करने के नियम हैं,
-
संशोधन से पहले और बाद में सरणी तत्वों के योग के बीच का अंतर S होना चाहिए।
-
संशोधित सरणी में नकारात्मक मानों की अनुमति नहीं है।
-
यदि संशोधित सरणी, सरणी के न्यूनतम मानों को अधिकतम करने की आवश्यकता है।
-
सरणी का संशोधन सरणी के किसी भी तत्व को बढ़ाकर या घटाकर किया जा सकता है ।
इन बाधाओं का उपयोग करते हुए, हमें नई सरणी खोजने और सरणी के सबसे छोटे तत्व के लिए अधिकतम मान वापस करने की आवश्यकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input : arr[] = {4, 5, 6} S = 2
Output : 4 स्पष्टीकरण
संशोधित सरणी है {4, 5, 5}
समाधान दृष्टिकोण
हमें संशोधित सरणी के सबसे छोटे मान को अधिकतम करने की आवश्यकता है। हम इसे 0 (सबसे छोटा संभव) के बीच के सबसे छोटे मान के लिए इष्टतम मान की बाइनरी खोज का उपयोग करके करेंगे। और गिरफ्तारी<उप>मिनट (सबसे बड़ा संभव)। हम सबसे छोटे संभव मान के लिए अंतर की जांच करेंगे।
कुछ विशेष शर्त,
यदि 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