Permutación creciente de los primeros N números naturales

Dada una permutación {P ₁ , P ₂ , P ₃ , ….. P _N ) de primeros N números naturales. La tarea es verificar si es posible hacer que la permutación aumente intercambiando dos números cualesquiera. Si ya está en orden creciente, no haga nada. 
Ejemplos: 
 

Entrada: a[] = {5, 2, 3, 4, 1} 
Salida: Sí 
Intercambiar 1 y 5
Entrada: a[] = {1, 2, 3, 4, 5} 
Salida: Sí 
Ya en orden creciente
Entrada: a[] = {5, 2, 1, 4, 3} 
Salida: No 
 

Enfoque: Sea K el número de posiciones i en las que P ₁ ≠ i (indexación basada en 1). Si K = 0 , la respuesta es Sí , ya que la permutación se puede dejar como está. Si K = 2 , la respuesta también es Sí : intercambie los dos elementos fuera de lugar. (Tenga en cuenta que K = 1 nunca es posible, ya que si algún elemento se coloca en la posición incorrecta, el elemento que debía estar en esa posición también debe estar fuera de lugar). Si K > 2 , la respuesta es No : un solo intercambio solo puede afectar a dos elementos y, por lo tanto, solo puede corregir como máximo dos desajustes.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if it is
// possible to make the permutation
// increasing by swapping any two numbers
bool isPossible(int a[], int n)
{
    // To count misplaced elements
    int k = 0;
 
    // Count all misplaced elements
    for (int i = 0; i < n; i++) {
        if (a[i] != i + 1)
            k++;
    }
 
    // If possible
    if (k <= 2)
        return true;
 
    return false;
}
 
// Driver code
int main()
{
    int a[] = { 5, 2, 3, 4, 1 };
    int n = sizeof(a) / sizeof(a[0]);
 
    if (isPossible(a, n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function that returns true if it is
// possible to make the permutation
// increasing by swapping any two numbers
static boolean isPossible(int a[], int n)
{
    // To count misplaced elements
    int k = 0;
 
    // Count all misplaced elements
    for (int i = 0; i < n; i++)
    {
        if (a[i] != i + 1)
            k++;
    }
 
    // If possible
    if (k <= 2)
        return true;
 
    return false;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 5, 2, 3, 4, 1 };
    int n = a.length;
 
    if (isPossible(a, n))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by Code_Mech

# Python3 implementation of the approach
 
# Function that returns true if it is
# possible to make the permutation
# increasing by swapping any two numbers
def isPossible(a, n) :
 
    # To count misplaced elements
    k = 0;
 
    # Count all misplaced elements
    for i in range(n) :
        if (a[i] != i + 1) :
            k += 1;
 
    # If possible
    if (k <= 2) :
        return True;
 
    return False;
 
# Driver code
if __name__ == "__main__" :
 
    a = [5, 2, 3, 4, 1 ];
    n = len(a);
 
    if (isPossible(a, n)) :
        print("Yes");
    else :
        print("No");
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
     
class GFG
{
     
// Function that returns true if it is
// possible to make the permutation
// increasing by swapping any two numbers
static Boolean isPossible(int []a, int n)
{
    // To count misplaced elements
    int k = 0;
 
    // Count all misplaced elements
    for (int i = 0; i < n; i++)
    {
        if (a[i] != i + 1)
            k++;
    }
 
    // If possible
    if (k <= 2)
        return true;
 
    return false;
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 5, 2, 3, 4, 1 };
    int n = a.Length;
 
    if (isPossible(a, n))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function that returns true if it is
// possible to make the permutation
// increasing by swapping any two numbers
function isPossible(a, n)
{
 
    // To count misplaced elements
    let k = 0;
 
    // Count all misplaced elements
    for (let i = 0; i < n; i++) {
        if (a[i] != i + 1)
            k++;
    }
 
    // If possible
    if (k <= 2)
        return true;
 
    return false;
}
 
// Driver code
    let a = [ 5, 2, 3, 4, 1 ];
    let n = a.length;
 
    if (isPossible(a, n))
        document.write("Yes");
    else
        document.write("No");
 
// This code is contributed by Manoj
</script>

Yes

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)