Programa Python3 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:

# 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.

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!