সি প্রোগ্রামের মানের মতো ফ্রিকোয়েন্সি সহ উপাদানগুলির জন্য অ্যারে পরিসরের প্রশ্ন?

এখানে আমরা একটি আকর্ষণীয় সমস্যা দেখতে পাব। আমরা এন উপাদান সহ একটি অ্যারে আছে. আমাদেরকে নিম্নরূপ −

Q(শুরু, শেষ) নির্দেশ করে যে একটি সংখ্যা 'p' ঠিক কতবার হয়েছে 'p' সংখ্যা শুরু থেকে শেষ পর্যন্ত।

সুতরাং যদি অ্যারেটি এরকম হয়:{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