একটি অ্যারে যদি ক্রমবর্ধমান ক্রমে সর্টেড থাকে এবং কোনো পজিশন থেকে রোটেট করা থাকে, তবে সেটি "সর্টেড অ্যান্ড রোটেটেড"। উদাহরণ: [5,6,7,1,2,3,4]
অ্যালগরিদম
- অ্যারে ট্রাভার্স করুন এবং গণনা করুন কতবার arr[i] > arr[(i+1)%n]
- যদি কাউন্ট ≤ 1 হয়, তবে সর্টেড অ্যান্ড রোটেটেড।
- কারণ সর্টেড অ্যারেতে ০বার, রোটেটেড সর্টেড এতে ১বার এই কন্ডিশন সত্য হয়।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
bool checkSortedAndRotated(int* arr, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > arr[(i + 1) % n]) count++;
}
return count <= 1;
}
int main() {
int arr[] = {5, 6, 7, 1, 2, 3, 4};
int n = sizeof(arr) / sizeof(int);
cout << (checkSortedAndRotated(arr, n) ? "True" : "False") << endl;
return 0;
}
আউটপুট
True
