सी प्रोग्राम में मान के समान आवृत्ति वाले तत्वों के लिए ऐरे रेंज क्वेरी?

यहां हम एक दिलचस्प समस्या देखेंगे। हमारे पास एन तत्वों के साथ एक सरणी है। हमें एक प्रश्न Q इस प्रकार करना है -

क्यू (आरंभ, अंत) इंगित करता है कि संख्या 'पी' के आने की संख्या शुरू से अंत तक ठीक 'पी' संख्या है।

तो अगर सरणी इस प्रकार है:{1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8}, और प्रश्न हैं -

Q(1, 8) - यहां 1 एक बार मौजूद है, और 3 बार 3 बार मौजूद है। तो जवाब है 2

Q(0, 2) - यहाँ 1 एक बार मौजूद है। तो जवाब है 1

एल्गोरिदम

क्वेरी(एस, ई) -

Begin
   get the elements and count the frequency of each element ‘e’ into one map
   count := count + 1
   for each key-value pair p, do
      if p.key = p.value, then
         count := count + 1
      done
      return count;
End

उदाहरण

#include <iostream>
#include <map>
using namespace std;
int query(int start, int end, int arr[]) {
   map<int, int> freq;
   for (int i = start; i <= end; i++) //get element and store frequency
      freq[arr[i]]++;
   int count = 0;
   for (auto x : freq)
      if (x.first == x.second) //when the frequencies are same, increase count 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[][3] = {{ 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 << "Answer for Query " << (i + 1) << " = " << query(start, end, A) << endl;
   }
}

आउटपुट

Answer for Query 1 = 1
Answer for Query 2 = 2
Answer for Query 3 = 1
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 0