একটি স্থানান্তর যেখানে প্রতিটি উপাদান তার আগে বা পরে উপাদানগুলির সংখ্যা নির্দেশ করে?

এই বিভাগে আমরা একটি সমস্যা দেখতে পাব। এখানে n উপাদান একটি অ্যারে দেওয়া হয়. আমাদের পরীক্ষা করতে হবে যে অ্যারের একটি স্থানান্তর বিদ্যমান আছে কিনা, যেমন প্রতিটি উপাদান তার আগে বা পরে উপস্থিত উপাদানগুলির সংখ্যা নির্দেশ করে৷

ধরুন অ্যারের উপাদানগুলি হল {2, 1, 3, 3}। উপযুক্ত স্থানান্তর হল {3, 1, 2, 3} এর মত। এখানে প্রথম 3টি নির্দেশ করে যে এর পাশে তিনটি উপাদান রয়েছে, 1টি নির্দেশ করে যে এর আগে শুধুমাত্র একটি উপাদান রয়েছে। 2টি নির্দেশ করে যে এর আগে দুটি উপাদান রয়েছে এবং শেষ 3টি নির্দেশ করে যে এটির আগে তিনটি উপাদান রয়েছে।

অ্যালগরিদম

Permutation চেক করুন(arr, n)

begin
   define a hashmap to hold frequencies. The key and value are of integer type of the map.
   for each element e in arr, do
      increase map[e] by 1
   done
   for i := 0 to n-1, do
      if map[i] is non-zero, then
         decrease map[i] by 1
      else if map[n-i-1] is non-zero, then
         decrease map[n-i-1] by 1
      else
         return false
      end if
   done
   return true
end

উদাহরণ

#include<iostream>
#include<map>
using namespace std;
bool checkPermutation(int arr[], int n) {
   map<int, int> freq_map;
   for(int i = 0; i < n; i++){ //get the frequency of each number
      freq_map[arr[i]]++;
   }
   for(int i = 0; i < n; i++){
      if(freq_map[i]){ //count number of elements before current element
         freq_map[i]--;
      } else if(freq_map[n-i-1]){ //count number of elements after current element
         freq_map[n-i-1]--;
      } else {
         return false;
      }
   }
   return true;
}
main() {
   int data[] = {3, 2, 3, 1};
   int n = sizeof(data)/sizeof(data[0]);
   if(checkPermutation(data, n)){
      cout << "Permutation is present";
   } else {
      cout << "Permutation is not present";
   }
}

আউটপুট

Permutation is present