मान लीजिए हमारे पास एक पूर्णांक सरणी arr और एक लक्ष्य मान target है, हमें पूर्णांक मान ढूंढना है जैसे कि जब हम दी गई सरणी में मान से बड़े सभी पूर्णांकों को मान के बराबर बदलते हैं, तो सरणी का योग लक्ष्य के यथासंभव निकट हो जाता है। यदि वे समान हैं, तो ऐसा न्यूनतम पूर्णांक लौटाएं। इसलिए यदि सरणी [4,9,3] है और लक्ष्य 10 है, तो आउटपुट 3 होगा क्योंकि 3 का उपयोग करने पर सरणी [3,3,3] होगी, इसलिए योग 9 है, जो 10 के निकटतम तत्व है।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
n := सरणी का आकार, avg := कुल / n, sum := 0 और cnt := 0 सेट करेंi = 0 से n-1तक:- यदि
arr[i] <= avg, तोsum := sum + arr[i], औरcntको 1 से बढ़ाएं
- यदि
- यदि
target - sum == 0, तोavgलौटाएं high := (target - sum) / (n - cnt) की सीलिंगlow := (target - sum) / (n - cnt) की फ्लोर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;
}
};
int main(){
vector<int> v = {4,9,3,2};
Solution ob;
cout << (ob.findBestValue(v, 10));
}
इनपुट
[4,9,3,2] 10
आउटपुट
3