मान लीजिए कि हमारे पास एक पूर्णांक सरणी गिरफ्तारी और एक लक्ष्य मान लक्ष्य है, तो हमें पूर्णांक मान को इस तरह खोजना होगा कि जब हम दिए गए सरणी में मान से बड़े सभी पूर्णांक मान के बराबर हों, तो सरणी का योग निकटतम हो जाता है लक्षित करना संभव है। यदि वे समान हैं, तो न्यूनतम ऐसा पूर्णांक लौटाएं। तो यदि सरणी [4,9,3] की तरह है और लक्ष्य 10 है, तो आउटपुट 3 का उपयोग करने के रूप में 3 होगा, सरणी [3,3,3] होगी, इसलिए योग 9 है, जो निकटतम तत्व है से 10.
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n :=सरणी का आकार, औसत :=कुल / n, सेट योग :=0 और cnt :=0
- मैं के लिए 0 से n - 1 की सीमा में
- अगर एआर [i] <=औसत, तो योग:=योग + एआर [i], और 1 से सीएनटी बढ़ाएं
- यदि लक्ष्य - योग =0, तो औसत लौटाएं
- उच्च :=(लक्ष्य - योग) / (n - cnt) की अधिकतम सीमा
- निम्न :=मंजिल (लक्ष्य - योग) / (n - cnt)
- lowDiff :=|target – (low*(n - cnt) + sum)|
- highDiff :=|target – (high*(n - cnt) + sum)|
- अगर लोडिफ <=हाईडिफ, तो लो रिटर्न
- उच्च वापसी।
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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