ধরুন আমাদের nums নামে একটি পূর্ণসংখ্যা অ্যারে এবং একটি পূর্ণসংখ্যা k আছে, যা থ্রেশহোল্ড মান, আমরা একটি ধনাত্মক পূর্ণসংখ্যা ভাজক বেছে নেব এবং সেটি দিয়ে সমস্ত অ্যারেকে ভাগ করব এবং ভাগফলের যোগফল বের করব। আমাদের সবচেয়ে ছোট ভাজক বের করতে হবে যাতে উপরে বর্ণিত ফলাফল থ্রেশহোল্ড মান k-এর চেয়ে কম বা সমান হয়। উদাহরণ − যদি nums = [1,2,5,9] এবং k = 6, তবে আউটপুট হবে 5। ভাজক ১ হলে যোগফল (1+2+5+9) = ১৭ পাওয়া যায়। ভাজক ৪ হলে যোগফল ৭ পাওয়া যায় (1+1+2+3), ভাজক ৫ হলে যোগফল হবে (1+1+1+2) = 5
এটি নিশ্চিত যে উত্তর থাকবে।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- ok নামে একটি মেথড সংজ্ঞায়িত করুন, এটি তিনটি প্যারামিটার নেবে x, array nums এবং k, এটি নিম্নরূপ হবে −
- sum := ০
- i = 0 থেকে nums-এর আকার – ১ পর্যন্ত
- sum := sum + nums[i] / x-এর সিলিং মান
- true ফেরত দিন, যদি sum <= k, অন্যথায় false
- আসল মেথড নিচের মতো হবে −
- low := 1 এবং high := inf সেট করুন
- যখন 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; } }; main(){ vector<int> v = {1,2,5,9}; Solution ob; cout << (ob.smallestDivisor(v, 6)); }ইনপুট
[1,2,5,9] 6
আউটপুট
5
