Número mínimo de operaciones de incremento/decremento tales que la array contenga todos los elementos del 1 al N

Dado un arreglo de N elementos, la tarea es convertirlo en una permutación (Cada número del 1 al N ocurre exactamente una vez) usando las siguientes operaciones un número mínimo de veces: 

• Incrementa cualquier número.
• Decrementar cualquier número.

Ejemplos: 

Input: arr[] = {1, 1, 4}
Output: 2
The array can be converted into [1, 2, 3]
by adding 1 to the 1st index i.e. 1 + 1 = 2
and decrementing 2nd index by 1 i.e. 4- 1 = 3

Input: arr[] = {3, 0}
Output: 2

The array can be converted into [2, 1]

Enfoque: Para minimizar el número de movimientos/operaciones, ordene la array dada y haga a[i] = i+1 (basado en 0) que tomará abs(i+1-a[i]) no. de operaciones para cada elemento.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum operations
long long minimumMoves(int a[], int n)
{
 
    long long operations = 0;
 
    // Sort the given array
    sort(a, a + n);
 
    // Count operations by assigning a[i] = i+1
    for (int i = 0; i < n; i++)
        operations += abs(a[i] - (i + 1));
 
    return operations;
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 3, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << minimumMoves(arr, n);
 
    return 0;
}

// Java implementation of the above approach
 
import java.util.*;
class solution
{
// Function to find the minimum operations
static long minimumMoves(int a[], int n)
{
  
    long operations = 0;
  
    // Sort the given array
    Arrays.sort(a);
  
    // Count operations by assigning a[i] = i+1
    for (int i = 0; i < n; i++)
        operations += (long)Math.abs(a[i] - (i + 1));
  
    return operations;
}
  
// Driver Code
public static void main(String args[])
{
    int arr[] = { 5, 3, 2 };
    int n = arr.length;
  
    System.out.print(minimumMoves(arr, n));
 
}
 
}
//contributed by Arnab Kundu

# Python 3 implementation of the above approach
 
# Function to find the minimum operations
def minimumMoves(a, n):
     
    operations = 0
    # Sort the given array
    a.sort(reverse = False)
     
    # Count operations by assigning a[i] = i+1
    for i in range(0,n,1):
        operations = operations + abs(a[i] - (i + 1))
 
    return operations
 
# Driver Code
if __name__ == '__main__':
    arr = [ 5, 3, 2 ]
    n = len(arr)
 
    print(minimumMoves(arr, n))
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the above approach
using System;
 
class GFG
{
// Function to find the minimum operations
static long minimumMoves(int []a, int n)
{
 
    long operations = 0;
 
    // Sort the given array
    Array.Sort(a);
 
    // Count operations by assigning
    // a[i] = i+1
    for (int i = 0; i < n; i++)
        operations += (long)Math.Abs(a[i] - (i + 1));
 
    return operations;
}
 
// Driver Code
static public void Main ()
{
    int []arr = { 5, 3, 2 };
    int n = arr.Length;
     
    Console.WriteLine(minimumMoves(arr, n));
}
}
 
// This code is contributed by Sach_Code

<?php
// PHP implementation of the above approach
// Function to find the minimum operations
 
function minimumMoves($a, $n)
{
    $operations = 0;
 
    // Sort the given array
    sort($a);
 
    // Count operations by assigning
    // a[i] = i+1
    for ($i = 0; $i < $n; $i++)
        $operations += abs($a[$i] -
                          ($i + 1));
 
    return $operations;
}
 
// Driver Code
$arr = array( 5, 3, 2 );
$n = sizeof($arr);
 
echo minimumMoves($arr, $n);
 
// This code is contributed by ajit
?>

<script>
 
// Javascript implementation of the above approach
 
// Function to find the minimum operations
function minimumMoves(a, n)
{
    let operations = 0;
 
    // Sort the given array
    a.sort();
 
    // Count operations by assigning
    // a[i] = i+1
    for(let i = 0; i < n; i++)
        operations += Math.abs(a[i] - (i + 1));
 
    return operations;
}
 
// Driver code
let arr = [ 5, 3, 2 ];
let n = arr.length;
   
document.write(minimumMoves(arr, n));
 
// This code is contributed by divyesh072019
 
</script>

4

Complejidad de tiempo: O (NlogN)

Espacio Auxiliar: O(1)