समस्या विवरण
एक सरणी arr[] दी गई है जिसमें धनात्मक पूर्णांक हैं। लक्ष्य arr[] के उन उपसरणियों की संख्या ज्ञात करना है जिनके तत्वों का औसत arr[] के शेष तत्वों के औसत से अधिक है जो उसमें मौजूद नहीं हैं।
उदाहरण
इनपुट
arr[] = { 3, 2, 4 }
आउटपुट
उप-सरणियों की संख्या: 2
व्याख्या
उपसरणियां: [3], [2], [4], [3,2], [2,4], [3,2,4]। [4] का औसत 4 है जो [2,3] के औसत से अधिक है। [3,2,4] का औसत 3 है जो [] के औसत से अधिक है।
इनपुट
arr[] = { 3, 3, 3 }
आउटपुट
उप-सरणियों की संख्या: 1
व्याख्या
उपसरणियां: [3], [3], [3], [3,3], [3,3], [3,3,3]। [3,3,3] का औसत 3 है जो [] के औसत से अधिक है।
दृष्टिकोण
इस दृष्टिकोण में एक प्रीफिक्स योग सरणी बनाएं जो इंडेक्स i तक के तत्वों का योग new_arr[i] में संग्रहीत करेगी। अब हमारे पास पिछले तत्व तक के योग हैं, फिर arr[i] तक का योग और तत्वों की संख्या j-i+1 के रूप में गणना करें और औसत निकालें।
एल्गोरिदम चरण
- एक सरणी
arr[]इनपुट के रूप में लें। - फंक्शन
count(int arr[], int size)arr[]लेता है और उन उप-सरणियों की संख्या लौटाता है जिनका औसत शेष तत्वों के औसत से अधिक है। - पिछले इंडेक्स तत्वों तक के योग को संग्रहीत करने के लिए सरणी
new_arr[size]लें। i=0सेi<sizeतक पार करें औरnew_arr[i]कोnew_arr[i-1] + arr[i-1]से सेट करें।- अब दो
forलूप का उपयोग करकेnew_arr[]को पार करें। - अब
total_1की गणना पिछले उपसरणियों के योग के रूप में करें। और इसमें तत्वcount_1के रूप में। total_2की गणना अगले उपसरणियों के योग के रूप में करें और इसमें तत्वcount_2के रूप में।- औसत की गणना करें:
check_1 = total_1 / count_1औरcheck_2 = total_2 / count_2। - यदि औसत
check_1 > check_2तो गिनती बढ़ाएं। forलूप के अंत में परिणाम के रूप में गिनती लौटाएं।
C++ कोड उदाहरण
#include <bits/stdc++.h>
using namespace std;
int count(int arr[], int size) {
int count = 0;
int new_size = size + 1;
int new_arr[new_size] = { 0 };
for (int i = 1; i < new_size; i++) {
new_arr[i] = new_arr[i - 1] + arr[i - 1];
}
for (int i = 1; i < new_size; i++) {
for (int j = i; j < new_size; j++) {
int total_1 = new_arr[j] - new_arr[i - 1];
int count_1 = j - i + 1;
int total_2 = new_arr[size] - total_1;
int count_2 = 0;
if((size - count_1) == 0) {
count_2 = 1;
} else {
count_2 = size - count_1;
}
int check_1 = total_1 / count_1;
int check_2 = total_2 / count_2;
if (check_1 > check_2) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = { 2, 6, 2, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "उप-सरणियों की संख्या: " << count(arr, size);
return 0;
}
आउटपुट
उप-सरणियों की संख्या: 6