Desarreglos mínimos presentes en la array de AP (progresión aritmética)

Dada una array de n elementos. La array dada es una permutación de alguna progresión aritmética. Encuentre el número mínimo de arreglos presentes en esa array para hacer de esa array una progresión aritmética.

Ejemplos:  

Input : arr[] = [8, 6, 10 ,4, 2]
Output : Minimum De-arrangement = 3
Explanation : arr[] = [10, 8, 6, 4, 2] is permutation 
which forms an AP and has minimum de-arrangements.

Input : arr[] = [5, 10, 15, 25, 20]
Output : Minimum De-arrangement = 2
Explanation : arr[] = [5, 10, 15, 20, 25] is permutation
which forms an AP and has minimum de-arrangements.

Según la propiedad de la progresión aritmética, nuestra secuencia será creciente o decreciente. Además, sabemos que el reverso de cualquier Progresión Aritmética también forma otra Progresión Aritmética. Por lo tanto, creamos una copia de la array original y luego, una vez que ordenamos nuestra array dada en orden creciente y encontramos el recuento total de discrepancias nuevamente, luego revertiremos nuestra array ordenada y encontraremos una nueva cuenta de discrepancias. Comparando ambos recuentos de desajustes, podemos encontrar el número mínimo de desarreglos.

// CPP for counting minimum de-arrangements present
// in an array.
#include<bits/stdc++.h>
using namespace std;
 
// function to count Dearrangement
int countDe (int arr[], int n)
{
    // create a copy of original array
    vector <int> v (arr, arr+n);
 
    // sort the array
    sort(arr, arr+n);
     
    // traverse sorted array for counting mismatches
    int count1 = 0;
    for (int i=0; i<n; i++)  
        if (arr[i] != v[i])
            count1++;       
     
    // reverse the sorted array
    reverse(arr,arr+n);   
 
    // traverse reverse sorted array for counting
    // mismatches
    int count2 = 0;
    for (int i=0; i<n; i++)
        if (arr[i] != v[i])      
            count2++;
 
    // return minimum mismatch count
    return (min (count1, count2));
}
 
// driver program
int main()
{
    int arr[] = {5, 9, 21, 17, 13};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum Dearrangement = " << countDe(arr, n);
    return 0;
}

// Java code for counting minimum
// de-arrangements present in an array.
import java.util.*;
import java.lang.*;
import java.util.Arrays;
 
public class GeeksforGeeks{
     
    // function to count Dearrangement
    public static int countDe(int arr[], int n){
        int v[] = new int[n];
         
        // create a copy of original array
        for(int i = 0; i < n; i++)
            v[i] = arr[i];
             
        // sort the array
        Arrays.sort(arr);
     
        // traverse sorted array for
        // counting mismatches
        int count1 = 0;
        for (int i = 0; i < n; i++)
            if (arr[i] != v[i])
            count1++;    
     
        // reverse the sorted array
        Collections.reverse(Arrays.asList(arr));
 
        // traverse reverse sorted array
        // for counting mismatches
        int count2 = 0;
        for (int i = 0; i < n; i++)
            if (arr[i] != v[i])    
                count2++;
 
        // return minimum mismatch count
        return (Math.min (count1, count2));
    }
 
    // driver code
    public static void main(String argc[]){
        int arr[] = {5, 9, 21, 17, 13};
        int n = 5;
        System.out.println("Minimum Dearrangement = "+
                            countDe(arr, n));
    }
}
 
/*This code is contributed by Sagar Shukla.*/

# Python3 code for counting minimum
# de-arrangements present in an array.
 
# function to count Dearrangement
def countDe(arr, n):
 
        i = 0
 
        # create a copy of
        # original array
        v = arr.copy()
             
        # sort the array
        arr.sort()
     
        # traverse sorted array for
        # counting mismatches
        count1 = 0
        i = 0
        while( i < n ):
            if (arr[i] != v[i]):
                count1 = count1 + 1
            i = i + 1
     
        # reverse the sorted array
        arr.sort(reverse=True)
 
        # traverse reverse sorted array
        # for counting mismatches
        count2 = 0
        i = 0
        while( i < n ):
            if (arr[i] != v[i]):    
                count2 = count2 + 1
            i = i + 1
 
        # return minimum mismatch count
        return (min (count1, count2))
 
# Driven code
arr = [5, 9, 21, 17, 13]
n = 5
print ("Minimum Dearrangement =",countDe(arr, n))
 
# This code is contributed by "rishabh_jain".

// C# code for counting
// minimum de-arrangements
// present in an array.
using System;
 
class GFG
{
 
// function to count
// Dearrangement
public static int countDe(int[] arr,
                          int n)
{
    int[] v = new int[n];
     
    // create a copy
    // of original array
    for(int i = 0; i < n; i++)
        v[i] = arr[i];
         
    // sort the array
    Array.Sort(arr);
 
    // traverse sorted array for
    // counting mismatches
    int count1 = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] != v[i])
        count1++;
 
    // reverse the sorted array
    Array.Reverse(arr);
 
    // traverse reverse sorted array
    // for counting mismatches
    int count2 = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] != v[i])
            count2++;
 
    // return minimum
    // mismatch count
    return (Math.Min (count1, count2));
}
 
// Driver code
public static void Main()
{
    int[] arr = new int[]{5, 9, 21, 17, 13};
    int n = 5;
    Console.WriteLine("Minimum Dearrangement = " +
                                 countDe(arr, n));
}
}
 
// This code is contributed by mits

<?php
// PHP for counting minimum de-arrangements
// present in an array.
 
// function to count Dearrangement
function countDe ($arr, $n)
{
    // create a copy of original array
    $v = $arr;
 
    // sort the array
    sort($arr);
     
    // traverse sorted array for
    // counting mismatches
    $count1 = 0;
    for ($i = 0; $i < $n; $i++)
        if ($arr[$i] != $v[$i])
            $count1++;
     
    // reverse the sorted array
    rsort($arr);
 
    // traverse reverse sorted array
    // for counting mismatches
    $count2 = 0;
    for ($i = 0; $i < $n; $i++)
        if ($arr[$i] != $v[$i])
            $count2++;
 
    // return minimum mismatch count
    return (min($count1, $count2));
}
 
// Driver Code
$arr = array(5, 9, 21, 17, 13);
$n = count($arr);
echo "Minimum Dearrangement = " .
               countDe($arr, $n);
 
// This code is contributed by mits
?>

<script>
 
// JavaScript code for counting minimum
// de-arrangements present in an array
 
// Function to count Dearrangement
function countDe(arr, n)
{
    let v = [];
       
    // Create a copy of original array
    for(let i = 0; i < n; i++)
        v[i] = arr[i];
           
    // Sort the array
    arr.sort();
   
    // Traverse sorted array for
    // counting mismatches
    let count1 = 0;
    for(let i = 0; i < n; i++)
        if (arr[i] != v[i])
            count1++;    
   
    // Reverse the sorted array
    arr.reverse();
 
    // Traverse reverse sorted array
    // for counting mismatches
    let count2 = 0;
    for(let i = 0; i < n; i++)
        if (arr[i] != v[i])    
            count2++;
 
    // Return minimum mismatch count
    return (Math.min (count1, count2));
}
 
// Driver Code
let arr = [ 5, 9, 21, 17, 13 ];
let n = 5;
 
document.write("Minimum Dearrangement = " +
               countDe(arr, n));
                
// This code is contributed by sanjoy_62
 
</script>

Producción: 

Minimum Dearrangement = 2

Complejidad de tiempo: O (nlogn).

Espacio Auxiliar: O(n)