मान लीजिए हमारे पास nums नामक पूर्णांकों की एक सरणी और एक पूर्णांक k है, जो थ्रेशहोल्ड मान है, हम एक धनात्मक पूर्णांक भाजक चुनेंगे और सभी सरणी को इससे विभाजित करेंगे और विभाजन के परिणाम को जोड़ेंगे। हमें सबसे छोटा भाजक ढूंढना है जैसे कि ऊपर उल्लिखित परिणाम थ्रेशहोल्ड मान k से कम या बराबर हो। उदाहरण के लिए: यदि nums = [1,2,5,9] और k = 6, तो आउटपुट 5 होगा। हम भाजक 1 होने पर योग (1+2+5+9) = 17 प्राप्त कर सकते हैं। यदि भाजक 4 है, तो हम योग 7 प्राप्त कर सकते हैं जैसे (1+1+2+3), जब भाजक 5 है, तो योग (1+1+1+2) = 5 होगा।
यह गारंटी है कि एक उत्तर होगा।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
checkनामक एक विधि परिभाषित करें, यह तीन पैरामीटर लेगी जैसेx, सरणी nums, और k, यह निम्नानुसार होगी:sum := 0i = 0 से nums का आकार - 1तक:sum := sum + nums[i] / x की सीलिंग मान
- यदि
sum <= kतो true लौटाएं, अन्यथा false
- वास्तविक विधि इस प्रकार होगी:
low := 1 और high := infसेट करेंwhile low < high:mid := low + (high - low)/2- यदि
check(mid, nums, k), तोhigh := mid, अन्यथाlow := mid + 1
highलौटाएं
उदाहरण
#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;
}
};
int main(){
vector<int> v = {1,2,5,9};
Solution ob;
cout << (ob.smallestDivisor(v, 6));
}
इनपुट
[1,2,5,9] 6
आउटपुट
5