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

इस खंड में हम एक समस्या देखेंगे। यहां 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 #include using namespace std; bool checkPermutation(int arr[], int n) {     map 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