Programa C++ para contar las rotaciones requeridas para ordenar la array dada en orden no creciente

Dada una array arr[] que consta de N enteros, la tarea es ordenar la array en orden no creciente por el número mínimo de rotaciones en sentido contrario a las agujas del reloj. Si no es posible ordenar la array, imprima «-1» . De lo contrario, imprima el recuento de rotaciones.

Ejemplos:

Entrada: arr[] = {2, 1, 5, 4, 3}
Salida: 2
Explicación: Se requieren dos rotaciones en sentido antihorario para clasificar la array en orden decreciente, es decir, {5, 4, 3, 2, 1}

Entrada: arr[] = {2, 3, 1}
Salida: -1

Enfoque: La idea es atravesar la array dada arr[] y contar el número de índices que satisfacen arr[i + 1] > arr[i] . Siga los pasos a continuación para resolver el problema:

• Almacene el recuento de arr[i + 1] > arr[i] en una variable y también almacene el índice cuando arr[i+1] > arr[i] .
• Si el valor de count es N – 1 , la array se ordena en orden no decreciente. Los pasos requeridos son exactamente (N – 1) .
• Si el valor de count es 0 , entonces la array ya está ordenada en orden no creciente.
• Si el valor de count es 1 y arr[0] ≤ arr[N – 1] , entonces el número requerido de rotaciones es igual a (index + 1) , al realizar el desplazamiento de todos los números hasta ese índice. Además, verifique si arr[0] ≤ arr[N – 1] para asegurarse de que la secuencia no sea creciente.
• De lo contrario, no es posible ordenar la array en orden no creciente.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to count minimum anti-
// clockwise rotations required to
// sort the array in non-increasing order
void minMovesToSort(int arr[], int N)
{
    // Stores count of arr[i + 1] > arr[i]
    int count = 0;
  
    // Store last index of arr[i+1] > arr[i]
    int index;
  
    // Traverse the given array
    for (int i = 0; i < N - 1; i++) {
  
        // If the adjacent elements are
        // in increasing order
        if (arr[i] < arr[i + 1]) {
  
            // Increment count
            count++;
  
            // Update index
            index = i;
        }
    }
  
    // Print the result according
    // to the following conditions
    if (count == 0) {
        cout << "0";
    }
    else if (count == N - 1) {
        cout << N - 1;
    }
    else if (count == 1
             && arr[0] <= arr[N - 1]) {
        cout << index + 1;
    }
  
    // Otherwise, it is not
    // possible to sort the array
    else {
        cout << "-1";
    }
}
  
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 1, 5, 4, 2 };
    int N = sizeof(arr)
            / sizeof(arr[0]);
  
    // Function Call
    minMovesToSort(arr, N);
  
    return 0;
}

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

¡ Consulte el artículo completo sobre las rotaciones de conteo requeridas para ordenar una array dada en orden no creciente para obtener más detalles!