C++ এ লক্ষ্যের সবচেয়ে কাছাকাছি পরিবর্তিত অ্যারের সমষ্টি

ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে অ্যারে এবং একটি টার্গেট ভ্যালু টার্গেট আছে, আমাদের পূর্ণসংখ্যার মানটি খুঁজে বের করতে হবে যাতে আমরা প্রদত্ত অ্যারের মানের থেকে বড় সমস্ত পূর্ণসংখ্যা পরিবর্তন করলে মানের সমান হবে, অ্যারের যোগফল যতটা কাছাকাছি হবে লক্ষ্য করা সম্ভব। যদি তারা একই হয়, তাহলে ন্যূনতম এই ধরনের পূর্ণসংখ্যা ফেরত দিন। সুতরাং যদি অ্যারেটি [4,9,3] এর মতো হয় এবং লক্ষ্য 10 হয়, তাহলে 3 ব্যবহার করে আউটপুট 3 হবে, অ্যারেটি হবে [3,3,3], তাই যোগফল 9, এটি নিকটতম উপাদান থেকে 10.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=অ্যারের আকার, গড় :=মোট / n, সমষ্টি :=0 এবং cnt :=0
• আমি 0 থেকে n – 1
  পরিসরে
  • যদি arr[i] <=avg হয়, তাহলে sum :=sum + arr[i], এবং cnt 1 দ্বারা বাড়ান
• যদি লক্ষ্য – যোগফল =0, তাহলে গড় ফেরত দিন
• উচ্চ :=(লক্ষ্য - যোগফল) / (n - cnt) এর সিলিং
• নিম্ন :=(লক্ষ্য - যোগফল) / (n - cnt)
• lowDiff :=|লক্ষ্য – (নিম্ন*(n - cnt) + যোগফল)|
• হাইডিফ :=|লক্ষ্য – (উচ্চ*(n - cnt) + যোগফল)|
• যদি lowDiff <=highDiff, তারপর কম দিন
• উচ্চ রিটার্ন।

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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