कार्य को देखते हुए तत्वों की अधिकतम संख्या को खोजने के लिए है जो किसी दिए गए सरणी में अपने तत्वों को अधिकतम k बार बढ़ाने के बाद बराबर बनाया जा सकता है।
आइए अब समझते हैं कि हमें एक उदाहरण का उपयोग करके क्या करना है -
इनपुट
a[] = {1, 3, 8}, k = 4 आउटपुट
2
स्पष्टीकरण
यहाँ हम 1 तीन बार वृद्धि करके और 3 चौगुनी वृद्धि करके दो चौके प्राप्त कर सकते हैं, जिससे a[] ={4, 4, 8}
हो जाता है।इनपुट
arr = {2, 5, 9}, k = 2 आउटपुट
0
निम्नलिखित कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है
-
मुख्य () फ़ंक्शन में int a[], आकार . प्रारंभ करें और k क्रमशः सरणी तत्वों, सरणी के आकार और अधिकतम संभव अद्यतनों को संग्रहीत करने के लिए।
-
अधिकतम () फ़ंक्शन में, पहले सरणी को आरोही क्रम में क्रमबद्ध करें और फिर दो और सरणियों की घोषणा करें int p[size + 1] और m[आकार + 1] जो क्रमशः उपसर्ग योग और अधिकतम मान संग्रहीत करेगा।
-
i =0 से i<=आकार तक लूप करें और p[i] =0 और m[i] =0 को प्रारंभ करें।
-
लूप के बाहर m[0] =arr[0] और p[0] =arr[0] डालें।
-
i =1 से i<आकार तक लूप करें और उपसर्ग योग की गणना करने के लिए p[i] =p[i - 1] + arr[i] डालें और m[i] =max(m[i - 1], arr[i] डालें ) उस स्थिति तक अधिकतम मान की गणना करने के लिए।
-
लूप के बाद, int Lt =1, Rt =size, परिणाम को क्रमशः बाएँ मान, दाएँ मान और अंतिम उत्तर को संग्रहीत करने के लिए प्रारंभ करें। उसके बाद बाइनरी सर्च शुरू करें।
-
शर्त के साथ लूप शुरू करें (Lt
-
अन्यथा सीधे शब्दों में Rt =मध्य -1 रखें।
-
लूप प्रिंट परिणाम के बाहर।
-
फ़ंक्शन में बूल EleCal() के लिए शर्त के साथ लूप के लिए आरंभ करें (int i =0, j =x; j <=size;j++, i++)
-
लूप के अंदर जांचें कि क्या (x * m[j] - (p[j] - p[i]) <=k)। यदि ऐसा है, तो सत्य लौटें। लूप के बाहर झूठी वापसी।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
bool EleCal(int p[], int m[], int x, int k, int size){
for (int i = 0, j = x; j <= size; j++, i++){
if (x * m[j] - (p[j] - p[i]) <= k)
return true;
}
return false;
}
void Max(int arr[], int size, int k){
// sorting array in ascending order
sort(arr, arr + size);
int p[size + 1];
//array for maximum value
int m[size + 1];
// Initialize prefix array and maximum array
for (int i = 0; i <= size; ++i){
p[i] = 0;
m[i] = 0;
}
m[0] = arr[0];
p[0] = arr[0];
for (int i = 1; i < size; i++){
// Calculating prefix sum of the array
p[i] = p[i - 1] + arr[i];
// Calculating max value upto that position
// in the array
m[i] = max(m[i - 1], arr[i]);
}
// Binary seach
int Lt = 1, Rt = size, result;
while (Lt < Rt){
int mid = (Lt + Rt) / 2;
if (EleCal(p, m, mid - 1, k, size)){
result = mid;
Lt = mid + 1;
}
else
Rt = mid - 1;
}
//answer
cout<<result;
}
// main function
int main(){
int a[] = { 1, 3, 8 };
int size = sizeof(a) / sizeof(a[0]);
int k = 4;
Max(a, size, k);
return 0;
} आउटपुट
2