Número máximo de puntos fijos usando al menos 1 intercambio

Dada una permutación de N elementos (los elementos están en el rango de 0 a N-1). Un punto fijo es un índice en el que el valor es el mismo que el índice (es decir, a[i]=i ). Tienes permitido hacer como máximo 1 intercambio. Encuentra el número máximo de puntos fijos que puedes obtener.
Ejemplos : 
 

Input : N = 5
        arr[] = {0, 1, 3, 4, 2}
Output : 3
2 and 3 can be swapped to get:
0 1 2 4 3
which has 3 fixed points.

Input : N = 5
        a[] = {0, 1, 2, 4, 3}
Output : 5 

Dado que solo se nos permite hacer 1 intercambio, la cantidad de puntos fijos se puede aumentar como máximo en 2.
Tengamos una array pos que mantenga la posición de cada elemento en la array de entrada. Ahora, recorremos la array y tenemos los siguientes casos: 
 

• Si a[i] = i. Simplemente podemos incrementar el conteo y seguir adelante.
• Si, pos[i] = a[i], lo que significa que el intercambio de los 2 términos haría que i y a[i] fueran puntos fijos, por lo tanto, aumentaría el conteo en 2. Tenga en cuenta que el intercambio se puede realizar al menos una vez.

Al final del recorrido, si no hemos hecho ningún intercambio, significa que nuestro intercambio no pudo aumentar la cuenta en 2, por lo que ahora si hay al menos 2 elementos que no son puntos fijos, podemos hacer un intercambio. para aumentar la cuenta en 1, es decir, convertir uno de esos puntos en un punto fijo.
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find maximum number of
// fixed points using atmost 1 swap
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum number of
// fixed points using atmost 1 swap
int maximumFixedPoints(int a[], int n)
{
    int i, pos[n], count = 0, swapped = 0;
 
    // Store position of each element in
    // input array
    for (i = 0; i < n; i++)
        pos[a[i]] = i;
 
    for (i = 0; i < n; i++) {
 
        // If fixed point, increment count
        if (a[i] == i)
            count++;
 
        // Else check if swapping increments
        // count by 2
        else if (swapped == 0 && pos[i] == a[i]) {
            count += 2;
            swapped = 1;
        }
    }
 
    // If not swapped yet and elements remaining
    if (swapped == 0 && count < n - 1)
        count++;
 
    return count;
}
 
// Driver Code
int main()
{
    int a[] = { 0, 1, 3, 4, 2 };
 
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << maximumFixedPoints(a, n);
 
    return 0;
}

// Java program to find maximum number of
// fixed points using atmost 1 swap
import java.io.*;
 
class GFG {
  
 
// Function to find maximum number of
// fixed points using atmost 1 swap
static int maximumFixedPoints(int a[], int n)
{
    int i, count = 0, swapped = 0;
    int pos[] = new int[n];
 
    // Store position of each element in
    // input array
    for (i = 0; i < n; i++)
        pos[a[i]] = i;
 
    for (i = 0; i < n; i++) {
 
        // If fixed point, increment count
        if (a[i] == i)
            count++;
 
        // Else check if swapping increments
        // count by 2
        else if (swapped == 0 && pos[i] == a[i]) {
            count += 2;
            swapped = 1;
        }
    }
 
    // If not swapped yet and elements remaining
    if (swapped == 0 && count < n - 1)
        count++;
 
    return count;
}
 
// Driver Code
 
    public static void main (String[] args) {
            int []a= { 0, 1, 3, 4, 2 };
 
    int n = a.length;
 
    System.out.println(maximumFixedPoints(a, n));
    }
}
 
 
// This code is contributed
// by shs

# Python3 program to find the maximum number
# of fixed points using at most 1 swap
 
# Function to find maximum number of
# fixed points using atmost 1 swap
def maximumFixedPoints(a, n):
 
    pos = [None] * n
    count, swapped = 0, 0
 
    # Store position of each element
    # in input array
    for i in range(0, n):
        pos[a[i]] = i
 
    for i in range(0, n):
     
        # If fixed point, increment count
        if a[i] == i:
            count += 1
 
        # Else check if swapping increments
        # count by 2
        elif swapped == 0 and pos[i] == a[i]:
            count += 2
            swapped = 1
 
    # If not swapped yet and elements remaining
    if swapped == 0 and count < n - 1:
        count += 1
 
    return count
 
# Driver Code
if __name__ == "__main__":
 
    a = [0, 1, 3, 4, 2]
    n = len(a)
 
    print(maximumFixedPoints(a, n))
 
# This code is contributed by Rituraj Jain

// C# program to find maximum number of
// fixed points using atmost 1 swap
using System;
 
class Program {
 
// Function to find maximum number of
// fixed points using atmost 1 swap
static int maximumFixedPoints(int []a, int n)
{
    int i, count = 0, swapped = 0;
    int []pos = new int[n];
 
    // Store position of each element in
    // input array
    for (i = 0; i < n; i++)
        pos[a[i]] = i;
 
    for (i = 0; i < n; i++) {
 
        // If fixed point, increment count
        if (a[i] == i)
            count++;
 
        // Else check if swapping increments
        // count by 2
        else if (swapped == 0 && pos[i] == a[i]) {
            count += 2;
            swapped = 1;
        }
    }
 
    // If not swapped yet and elements remaining
    if (swapped == 0 && count < n - 1)
        count++;
 
    return count;
}
 
    // Driver Code
    static void Main()
    {
        int []a= { 0, 1, 3, 4, 2 };
 
        int n = a.Length;
 
        Console.WriteLine(maximumFixedPoints(a, n));
    }
}
 
// This code is contributed
// by ANKITRAI1

<?php
// PHP program to find maximum number of
// fixed points using atmost 1 swap
 
// Function to find maximum number of
// fixed points using atmost 1 swap
function  maximumFixedPoints($a, $n)
{
    $i; $pos[$n]=array();
    $count = 0;
    $swapped = 0;
 
    // Store position of each element in
    // input array
    for ($i = 0; $i < $n; $i++)
        $pos[$a[$i]] = $i;
 
    for ($i = 0; $i < $n; $i++) {
 
        // If fixed point, increment count
        if ($a[$i] == $i)
            $count++;
 
        // Else check if swapping increments
        // count by 2
        else if ($swapped == 0 && $pos[$i] == $a[$i]) {
            $count += 2;
            $swapped = 1;
        }
    }
 
    // If not swapped yet and elements remaining
    if ($swapped == 0 && $count < $n - 1)
        $count++;
 
    return $count;
}
 
// Driver Code
     $a = array (0, 1, 3, 4, 2 );
        $n = sizeof($a) / sizeof($a[0]);
 
    echo maximumFixedPoints($a, $n);
 
 
// This code is contributed by Sachin
?>

<script>
    // Javascript program to find maximum number of
    // fixed points using atmost 1 swap
     
    // Function to find maximum number of
    // fixed points using atmost 1 swap
    function maximumFixedPoints(a, n)
    {
        let i, count = 0, swapped = 0;
        let pos = new Array(n);
 
        // Store position of each element in
        // input array
        for (i = 0; i < n; i++)
            pos[a[i]] = i;
 
        for (i = 0; i < n; i++) {
 
            // If fixed point, increment count
            if (a[i] == i)
                count++;
 
            // Else check if swapping increments
            // count by 2
            else if (swapped == 0 && pos[i] == a[i]) {
                count += 2;
                swapped = 1;
            }
        }
 
        // If not swapped yet and elements remaining
        if (swapped == 0 && count < n - 1)
            count++;
 
        return count;
    }
     
    let a= [ 0, 1, 3, 4, 2 ];
   
    let n = a.length;
 
    document.write(maximumFixedPoints(a, n));
     
    // This code is contributed by divyesh072019.
</script>

3

Complejidad de tiempo: O(N)