Compruebe si la permutación dada de 1 a N se puede contar en sentido horario o antihorario

Dada una array de enteros arr de tamaño N que contiene elementos distintos de 1 a N . La tarea es verificar si se puede encontrar una posición en la array de modo que todos los números del 1 al N se puedan contar en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj. 
Ejemplos:

Input: arr[] = [2, 3, 4, 5, 1]
Output: YES
Explanation:
                    1   2 
                  5       3
                      4
If counting is start at index 4
then all numbers can be counted
from 1 to N in a clockwise order.

Input: arr[] = {1, 2, 3, 5, 4]
Output: NO
Explanation: 
There is no any index in array
from which given array can count
1 to N in clockwise order or
counterclockwise order.

Enfoque: El problema anterior se puede resolver mediante la observación y el análisis.

1. Un índice en la array se puede encontrar solo si el recuento de la diferencia absoluta entre los elementos consecutivos mayores que 1 es exactamente 1 , porque solo entonces será posible contar de 1 a N en el sentido de las agujas del reloj o en el sentido contrario.
2. Si el conteo de la diferencia absoluta entre los elementos adyacentes es mayor que 1 , entonces será imposible contar de 1 a N en sentido horario o antihorario.

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

// C++ program to check Clockwise or
// counterclockwise order in an array
 
#include <bits/stdc++.h>
using namespace std;
 
bool check_order(vector<int> arr)
{
    int cnt = 0;
    for (int i = 0; i < arr.size() - 1; i++) {
        if (abs(arr[i + 1] - arr[i]) > 1)
            cnt++;
    }
    // Comparing the first and last
    // value of array
    if (abs(arr[0] - arr[arr.size() - 1]) > 1)
        cnt++;
 
    // If the Count is greater
    // than 1 then it can't be
    // represented in required order
    if (cnt > 1)
        return false;
    return true;
}
 
// Driver function
int main()
{
    vector<int> arr = { 2, 3, 4, 5, 1 };
    if (check_order(arr))
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

// Java program to check clockwise or
// counterclockwise order in an array
class GFG{
 
static boolean check_order(int []arr)
{
    int cnt = 0;
    for(int i = 0; i < arr.length - 1; i++)
    {
        if (Math.abs(arr[i + 1] -
                     arr[i]) > 1)
            cnt++;
    }
     
    // Comparing the first and last
    // value of array
    if (Math.abs(arr[0] -
                 arr[arr.length - 1]) > 1)
        cnt++;
 
    // If the Count is greater
    // than 1 then it can't be
    // represented in required order
    if (cnt > 1)
        return false;
         
    return true;
}
 
// Driver code
public static void main(String[] args)
{
    int []arr = { 2, 3, 4, 5, 1 };
     
    if (check_order(arr))
        System.out.print("YES");
    else
        System.out.print("NO");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to check clockwise or
# counterclockwise order in an array
def check_order(arr):
     
    cnt = 0
    for i in range(len(arr) - 1):
        if (abs(arr[i + 1] - arr[i]) > 1):
            cnt += 1
 
    # Comparing the first and last
    # value of array
    if (abs(arr[0] - arr[len(arr) - 1]) > 1):
        cnt += 1
 
    # If the count is greater
    # than 1 then it can't be
    # represented in required order
    if (cnt > 1):
        return False
         
    return True
 
# Driver code
arr = [ 2, 3, 4, 5, 1 ]
 
if (check_order(arr)):
    print("YES")
else:
    print("NO")
 
# This code is contributed by Vishal Maurya.

// C# program to check clockwise or
// counterclockwise order in an array
using System;
 
class GFG{
 
static bool check_order(int []arr)
{
    int cnt = 0;
     
    for(int i = 0; i < arr.Length - 1; i++)
    {
        if (Math.Abs(arr[i + 1] -
                   arr[i]) > 1)
            cnt++;
    }
     
    // Comparing the first and last
    // value of array
    if (Math.Abs(arr[0] -
                 arr[arr.Length - 1]) > 1)
        cnt++;
 
    // If the Count is greater
    // than 1 then it can't be
    // represented in required order
    if (cnt > 1)
        return false;
         
    return true;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 2, 3, 4, 5, 1 };
     
    if (check_order(arr))
        Console.Write("YES");
    else
        Console.Write("NO");
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript program to check clockwise or
// counterclockwise order in an array   
function check_order(arr)
{
        var cnt = 0;
        for (i = 0; i < arr.length - 1; i++)
        {
            if (Math.abs(arr[i + 1] - arr[i]) > 1)
                cnt++;
        }
 
        // Comparing the first and last
        // value of array
        if (Math.abs(arr[0] - arr[arr.length - 1]) > 1)
            cnt++;
 
        // If the Count is greater
        // than 1 then it can't be
        // represented in required order
        if (cnt > 1)
            return false;
 
        return true;
    }
 
    // Driver code
     
        var arr = [ 2, 3, 4, 5, 1 ];
 
        if (check_order(arr))
            document.write("YES");
        else
            document.write("NO");
 
// This code contributed by gauravrajput1
 
</script>

YES

Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.