Programa C++ para modificar una array dada a una array no decreciente por rotación

Dada una array arr[] de tamaño N (que consta de duplicados), la tarea es verificar si la array dada se puede convertir en una array no decreciente al rotarla. Si no es posible hacerlo, escriba “ No ”. De lo contrario, escriba “ Sí ”.

Ejemplos:

Entrada: arr[] = {3, 4, 5, 1, 2}
Salida: Sí
Explicación:  Después de 2 rotaciones a la derecha, la array arr[] se modifica a {1, 2, 3, 4, 5}

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

Enfoque: La idea se basa en el hecho de que se puede obtener un máximo de N arrays distintas rotando la array dada y verificando para cada array rotada individual, si es no decreciente o no. Siga los pasos a continuación para resolver el problema:

• Inicialice un vector , digamos v, y copie todos los elementos de la array original en él.
• Ordenar el vector v .
• Atraviese la array original y realice los siguientes pasos:
  • Rotar de 1 en cada iteración.
  • Si la array se vuelve igual al vector v , imprima » Sí «. De lo contrario, escriba “ No ”.

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 check if a
// non-decreasing array can be obtained
// by rotating the original array
void rotateArray(vector<int>& arr, int N)
{
    // Stores copy of original array
    vector<int> v = arr;
  
    // Sort the given vector
    sort(v.begin(), v.end());
  
    // Traverse the array
    for (int i = 1; i <= N; ++i) {
  
        // Rotate the array by 1
        rotate(arr.begin(),
               arr.begin() + 1, arr.end());
  
        // If array is sorted
        if (arr == v) {
  
            cout << "YES" << endl;
            return;
        }
    }
  
    // If it is not possible to
    // sort the array
    cout << "NO" << endl;
}
  
// Driver Code
int main()
{
    // Given array
    vector<int> arr = { 3, 4, 5, 1, 2 };
  
    // Size of the array
    int N = arr.size();
  
    // Function call to check if it is possible
    // to make array non-decreasing by rotating
    rotateArray(arr, N);
}

YES

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

¡ Consulte el artículo completo sobre Modificar una array dada a una array no decreciente por rotación para obtener más detalles!