ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে arr এবং একটি টার্গেট মান target আছে, আমাদের একটি পূর্ণসংখ্যা মান বের করতে হবে যাতে যখন আমরা দেওয়া অ্যারেতে value-এর চেয়ে বড় সব পূর্ণসংখ্যাকে value-এর সমান করি, অ্যারেটির যোগফল target-এর যতটা সম্ভব নিকট হয়। যদি তারা সমান হয়, তবে ন্যূনতম এমন পূর্ণসংখ্যা ফেরত দিন। তাই যদি অ্যারেটি হয় [4,9,3] এবং target 10 হয়, তবে আউটপুট হবে 3 কারণ 3 ব্যবহার করলে অ্যারে হবে [3,3,3], তাই যোগফল 9, যা 10-এর নিকটতম উপাদান।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- n := অ্যারেতে আকার, avg := total / n, sum := 0 এবং cnt := 0 সেট করুন
- i = 0 থেকে n – ১ পর্যন্ত
- যদি arr[i] <= avg, তবে sum := sum + arr[i], এবং cnt ১ বৃদ্ধি করুন
- যদি target – sum = 0, তবে avg ফেরত দিন
- high := (target - sum) / (n - cnt)-এর ceiing
- low := (target - sum) / (n - cnt)-এর floor
- lowDiff := |target – (low*(n - cnt) + sum)|
- highDiff := |target – (high*(n - cnt) + sum)|
- যদি lowDiff <= highDiff, তবে low ফেরত দিন
- high ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int findBestValue(vector<int>& arr, int target) { int n = arr.size(); int avg = target / n; int sum = 0; int cnt = 0; for(int i = 0; i < n; i++){ if(arr[i] <= avg){ sum += arr[i]; cnt++; } } if(target - sum == 0)return avg; int high = ceil(((target - sum) * 1.0)/ ((n - cnt) * 1.0)); int low = floor(((target - sum) * 1.0) / ((n - cnt) * 1.0)); int lowDiff = abs(target - (low * (n - cnt) + sum)); int highDiff = abs(target - (high * (n - cnt) + sum)); if( lowDiff <= highDiff)return low; return high; } }; main(){ vector<int> v = {4,9,3,2}; Solution ob; cout << (ob.findBestValue(v, 10)); }ইনপুট
[4,9,3,2] 10
আউটপুট
3
