समस्या विवरण
यहां हम एक दिलचस्प समस्या देखेंगे। हमारे पास N तत्वों वाला एक ऐरे है। हमें एक क्वेरी Q निष्पादित करनी है: Q(start, end) इंगित करता है कि एक संख्या 'p' शुरू से अंत तक ठीक 'p' बार आती है।
उदाहरण
ऐरे: {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8}
Q(1, 8): यहां 1 एक बार मौजूद है, और 3 तीन बार मौजूद है। तो उत्तर 2 है।
Q(0, 2): यहां 1 एक बार मौजूद है। तो उत्तर 1 है।
एल्गोरिदम
query(s, e)
शुरुआत
तत्व प्राप्त करें और प्रत्येक तत्व 'e' की आवृत्ति को एक मैप में गिनें
count := count + 1
प्रत्येक कुंजी-मान जोड़ी p के लिए
यदि p.key = p.value, तो
count := count + 1
अंत
वापस count
अंत
C++ प्रोग्राम उदाहरण
#include <iostream>
#include <map>
using namespace std;
int query(int start, int end, int arr[]) {
map freq;
for (int i = start; i <= end; i++)
freq[arr[i]]++;
int count = 0;
for (auto x : freq)
if (x.first == x.second)
count++;
return count;
}
int main() {
int A[] = {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8};
int n = sizeof(A) / sizeof(A[0]);
int queries[][2] = {{0, 1}, {1, 8}, {0, 2}, {1, 6}, {3, 5}, {7, 9}};
int query_count = sizeof(queries) / sizeof(queries[0]);
for (int i = 0; i < query_count; i++) {
int start = queries[i][0];
int end = queries[i][1];
cout << "क्वेरी " << (i + 1) << " का उत्तर = " << query(start, end, A) << endl;
}
}
आउटपुट
क्वेरी 1 का उत्तर = 1 क्वेरी 2 का उत्तर = 2 क्वेरी 3 का उत्तर = 1 क्वेरी 4 का उत्तर = 1 क्वेरी 5 का उत्तर = 1 क्वेरी 6 का उत्तर = 0
