ধরুন আমাদের কাছে একটি পূর্ণসংখ্যার অ্যারে আছে যাকে nums বলা হয় এবং একটি পূর্ণসংখ্যা k, অর্থাৎ থ্রেশহোল্ড মান, আমরা একটি ধনাত্মক পূর্ণসংখ্যা ভাজক নির্বাচন করব এবং এটি দ্বারা সমস্ত অ্যারেকে ভাগ করব এবং বিভাজনের ফলাফল যোগ করব। আমাদেরকে সবচেয়ে ছোট ভাজকটি খুঁজে বের করতে হবে যাতে উপরে উল্লিখিত ফলাফলটি থ্রেশহোল্ড মানের k এর থেকে কম বা সমান হয়। উদাহরণস্বরূপ − যদি nums =[1,2,5,9] এবং k =6 হয়, তাহলে আউটপুট হবে 5। আমরা যোগফল পেতে পারি (1+2+5+9) =17 যখন ভাজক 1 হয়। যদি ভাজক 4 হয়, তাহলে আমরা যোগফল 7 পেতে পারি (1+1+2+3), যখন ভাজক 5 হয়, তখন যোগফল হবে (1+1+1+2) =5
এটা নিশ্চিত যে একটি উত্তর হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- চেক নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি x, অ্যারে সংখ্যা এবং k এর মত তিনটি প্যারামিটার নেবে, এটি নিম্নরূপ হবে -
- সমষ্টি :=0
- আমি পরিসীমা 0 থেকে সংখ্যার আকার – 1
- সমষ্টি :=যোগফল + সংখ্যার সিলিং মান[i] / x
- সত্য ফেরত দিন, যদি যোগফল <=k হয়, অন্যথায় মিথ্যা
- প্রকৃত পদ্ধতি নিচের মত হবে -
- নিম্ন সেট করুন :=1 এবং উচ্চ :=inf
- যদিও কম <উচ্চ
- মধ্য :=নিম্ন + (উচ্চ – নিম্ন)/2
- যদি চেক (মধ্য, সংখ্যা, কে), তারপর উচ্চ :=মধ্য, অন্যথায় নিম্ন :=মধ্য + 1
- উচ্চ রিটার্ন
- আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(int x, vector <int> &nums, int th){
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += ceil((double)nums[i]/(double)x);
}
return sum<=th;
}
int smallestDivisor(vector<int>& nums, int th) {
int low = 1;
int high = 1e7;
while(low < high){
int mid = low + (high - low)/2;
if(ok(mid, nums, th)){
high = mid;
}else low = mid + 1;
}
return high;
}
};
main(){
vector<int> v = {1,2,5,9};
Solution ob;
cout << (ob.smallestDivisor(v, 6));
} ইনপুট
[1,2,5,9] 6
আউটপুট
5
