Kiểm tra mảng đã sắp xếp và xoay trong C++

Cho mảng số nguyên, kiểm tra có phải mảng tăng dần bị xoay (rotated) hay không.

Ví dụ

N = [7, 8, 9, 4, 5, 6] → True (tăng dần, xoay sau vị trí 3)

N = [1, 5, 7, 6, 2, 3] → False (không tăng, không xoay đúng)

Cách tiếp cận

Mảng sorted & rotated → có đúng 1 vị trí i mà arr[i] > arr[(i+1)%n].

• Đếm số cặp arr[i] > arr[(i+1)%n]
• Nếu count <= 1 → True, else False

Code C++

#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);
    if (checkSortedandRotated(arr, n)) cout << "True" << endl;
    else cout << "False" << endl;
    return 0;
}

Kết quả

True

Mảng [5,6,7,1,2,3,4] sorted và rotated tại vị trí 3.