Modificar 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);
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
  // Function to check if a
  // non-decreasing array can be obtained
  // by rotating the original array
  static void rotateArray(int[] arr, int N)
  {
    // Stores copy of original array
    int[] v = arr;
 
    // Sort the given vector
    Arrays.sort(v);
 
    // Traverse the array
    for (int i = 1; i <= N; ++i) {
 
      // Rotate the array by 1
      int x = arr[N - 1];
      i = N - 1;
      while(i > 0){
        arr[i] = arr[i - 1];
        arr[0] = x;
        i -= 1;
      }
 
      // If array is sorted
      if (arr == v) {
 
        System.out.print("YES");
        return;
      }
    }
 
    // If it is not possible to
    // sort the array
    System.out.print("NO");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Given array
    int[] arr = { 3, 4, 5, 1, 2 };
 
    // Size of the array
    int N = arr.length;
 
    // Function call to check if it is possible
    // to make array non-decreasing by rotating
    rotateArray(arr, N);
  }
}
 
// This code is contributed by splevel62.

# Python 3 program for the above approach
 
 
# Function to check if a
# non-decreasing array can be obtained
# by rotating the original array
def rotateArray(arr, N):
   
    # Stores copy of original array
    v = arr
 
    # Sort the given vector
    v.sort(reverse = False)
 
    # Traverse the array
    for i in range(1, N + 1, 1):
       
        # Rotate the array by 1
        x = arr[N - 1]
        i = N - 1
        while(i > 0):
            arr[i] = arr[i - 1]
            arr[0] = x
            i -= 1
             
        # If array is sorted
        if (arr == v):
            print("YES")
            return
 
    # If it is not possible to
    # sort the array
    print("NO")
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr =  [3, 4, 5, 1, 2]
 
    # Size of the array
    N = len(arr)
 
    # Function call to check if it is possible
    # to make array non-decreasing by rotating
    rotateArray(arr, N)
     
    # This code is contributed by ipg2016107.

// C# program to implement
// the above approach
using System;
class GFG
{
   
  // Function to check if a
  // non-decreasing array can be obtained
  // by rotating the original array
  static void rotateArray(int[] arr, int N)
  {
     
    // Stores copy of original array
    int[] v = arr;
 
    // Sort the given vector
    Array.Sort(v);
 
    // Traverse the array
    for (int i = 1; i <= N; ++i) {
 
      // Rotate the array by 1
      int x = arr[N - 1];
      i = N - 1;
      while(i > 0){
        arr[i] = arr[i - 1];
        arr[0] = x;
        i -= 1;
      }
 
      // If array is sorted
      if (arr == v) {
 
        Console.Write("YES");
        return;
      }
    }
 
    // If it is not possible to
    // sort the array
    Console.Write("NO");
  }
 
 
// Driver code
public static void Main()
{
    // Given array
    int[] arr = { 3, 4, 5, 1, 2 };
 
    // Size of the array
    int N = arr.Length;
 
    // Function call to check if it is possible
    // to make array non-decreasing by rotating
    rotateArray(arr, N);
}
}
 
// This code is contributed by susmitakundugoaldanga.

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to check if a
// non-decreasing array can be obtained
// by rotating the original array
function rotateArray(arr, N) {
 
    // Stores copy of original array
    let v = arr;
 
    // Sort the given vector
    v.sort((a, b) => a - b);
 
    // Traverse the array
    for (let i = 1; i <= N; ++i) {
 
        // Rotate the array by 1
        let x = arr[N - 1];
        i = N - 1;
        while (i--) {
            arr[i] = arr[i - 1];
            arr[0] = x;
        }
 
        // If array is sorted
 
        let isEqual = arr.every((e, i) => {
            return arr[i] == v[i]
        })
 
 
        if (isEqual) {
            document.write("YES");
            return;
        }
    }
 
    // If it is not possible to
    // sort the array
    document.write("NO");
}
 
 
// Driver code
 
// Given array
let arr = [3, 4, 5, 1, 2];
 
// Size of the array
let N = arr.length;
 
// Function call to check if it is possible
// to make array non-decreasing by rotating
rotateArray(arr, N);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

YES

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