एक क्रमपरिवर्तन जहां प्रत्येक तत्व उसके पहले या बाद में तत्वों की संख्या को इंगित करता है?

इस खंड में हम एक समस्या देखेंगे। यहाँ n तत्व एक सरणी में दिए गए हैं। हमें यह जांचना होगा कि क्या उस सरणी का क्रमपरिवर्तन मौजूद है, जैसे कि प्रत्येक तत्व उसके पहले या बाद में मौजूद तत्वों की संख्या को इंगित करता है।

मान लीजिए कि सरणी तत्व {2, 1, 3, 3} हैं। उपयुक्त क्रमपरिवर्तन {3, 1, 2, 3} जैसा है। यहां पहला 3 इंगित कर रहा है कि इसके आगे तीन तत्व हैं, 1 इंगित करता है कि इससे पहले केवल एक तत्व है। 2 इंगित करता है कि इसके पहले दो तत्व हैं और अंतिम 3 इंगित करता है कि इसके पहले तीन तत्व हैं।

एल्गोरिदम

checkPermutation(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