এই সমস্যায়, আমাদেরকে n আকারের একটি অ্যারে [] এবং একটি সংখ্যা S দেওয়া হয়েছে। আমাদের কাজ হল পরিবর্তিত অ্যারের সর্বনিম্ন মানের সর্বাধিক সম্ভাব্য মান খুঁজে বের করা .
এখানে, অ্যারে পরিবর্তন করার নিয়ম আছে,
-
পরিবর্তনের আগে এবং পরে অ্যারের উপাদানগুলির যোগফলের মধ্যে পার্থক্য S.
হওয়া উচিত -
পরিবর্তিত অ্যারেতে নেতিবাচক মান অনুমোদিত নয়৷
৷ -
পরিবর্তিত অ্যারে হলে, অ্যারের ন্যূনতম মান সর্বাধিক করা প্রয়োজন।
-
অ্যারের পরিবর্তন অ্যারের যেকোনো উপাদান বৃদ্ধি বা হ্রাস করে করা যেতে পারে .
এই সীমাবদ্ধতাগুলি ব্যবহার করে, আমাদের নতুন অ্যারে খুঁজে বের করতে হবে এবং অ্যারের ক্ষুদ্রতম উপাদানটির জন্য সর্বাধিক মান ফেরত দিতে হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : arr[] = {4, 5, 6} S = 2
Output : 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
