Tìm số lần xoay của mảng đã sắp xếp bị xoay trong C++

Cho mảng đã sắp xếp nhưng bị xoay (rotated sorted array). Tìm số lần xoay (xoay phải sang trái) để đưa về mảng sắp xếp. Ví dụ {15, 17, 1, 2, 6, 11} → xoay 2 lần thành {1, 2, 6, 11, 15, 17}.

Quan sát: số lần xoay = chỉ số của phần tử nhỏ nhất trong mảng.

Ví dụ

#include <iostream>
using namespace std;

int getMinIndex(int arr[], int n){
    int index = 0;
    for(int i = 1; i<n; i++){
        if(arr[i] < arr[index]){
            index = i;
        }
    }
    return index;
}

int countNumberOfRotations(int arr[], int n){
    return getMinIndex(arr, n);
}

int main() {
    int arr[] = {15, 17, 1, 2, 6, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Number of required rotations: " << countNumberOfRotations(arr, n);
}

Kết quả

Number of required rotations: 2