মান করুন আমাদের [0, 1, ..., N - 1]-এর একটি পারমুটেশন A দেওয়া আছে, যেখানে N হল A-র দৈর্ঘ্য। এখন (গ্লোবাল) ইনভার্সনের সংখ্যা হল i < j যাতে 0 <= i < j < N এবং A[i] > A[j]। আর লোকাল ইনভার্সনের সংখ্যা হল i যাতে 0 <= i < N এবং A[i] > A[i+1]। আমাদের true ফেরত দিতে হবে যদি এবং কেবল যদি গ্লোবাল ইনভার্সনের সংখ্যা লোকাল ইনভার্সনের সংখ্যার সমান হয়।
যদি ইনপুট হয় [1,0,2], তবে true ফেরত দেবে, কারণ শুধু একটি লোকাল ইনভার্সন এবং একটি গ্লোবাল ইনভার্সন আছে।
এটি সমাধান করার জন্য নিচের ধাপগুলি অনুসরণ করুন −
maxVal := -1,n := A-র আকারi = 0থেকেn - 3পর্যন্তmaxVal := max(A[i], maxVal)- যদি
maxVal > A[i + 2]হয়, তবে false ফেরত দিন
- true ফেরত দিন
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isIdealPermutation(vector<int>& A) {
int maxVal = -1;
int n = A.size();
for(int i = 0; i < n - 2; i++){
maxVal = max(A[i], maxVal);
if(maxVal > A[i + 2])
return false;
}
return true;
}
};
main(){
vector<int> v = {1,0,2};
Solution ob;
cout << (ob.isIdealPermutation(v));
}
ইনপুট
[1,0,2]
আউটপুট
1
