Minimice las operaciones de incremento o decremento para hacer que los elementos de Array sean consecutivos

Dada una array , arr[] de tamaño N ., la tarea es realizar operaciones mínimas de incremento o decremento en los elementos de la array, para hacer que todos los elementos sean consecutivos, generar la suma mínima de todos los cambios posibles (sumas y restas) obligado a hacer lo mismo.

Ejemplos :

Entrada: N = 5, arr[] = {13, 6, 11, 18, 4}
Salida: 15
Explicación: Convierta 4 a 9, 8 a 10, 13 a 12 y 18 a 13, la nueva array se convierte en {9, 10, 11 , 12, 13}. 
Así que la suma de los cambios es abs(9-4) + abs(10-8) + abs(12-13) + abs(13-18) = 15.

Entrada: N = 2, arr[] = {3, 8}
Salida: 4

Enfoque: La tarea se puede resolver usando observaciones. La mediana de los elementos de la array debe permanecer sin cambios y el resto de los elementos deben cambiarse en consecuencia, de modo que todos los elementos se vuelvan consecutivos .
Siga los pasos a continuación para resolver el problema:

• Ordenar la array
• Tome una variable mid que almacene la mediana de la array y una variable pos para almacenar su posición.
• Además, tome una variable ele e inicialícela con el valor más pequeño de la array de resultados, es decir, (mid – pos) y una variable sum = 0 para almacenar la suma de todos los cambios posibles en los elementos de la array.
• Iterar sobre la array y en cada i-ésima iteración:
  • Incrementar suma con abs(arr[i]-ele) (agregando la diferencia del elemento original y requerido)
  • Incrementar elemento con 1
• Salida de la suma.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to output sum of all the
// required changes in array
int minChanges(int arr[], int N)
{
    sort(arr, arr + N);
 
    // Stores median of array
    int mid = arr[N / 2];
 
    // Variable for position of median
    int pos = N / 2;
 
    // Smallest element of
    // the required array
    int ele = mid - pos;
    int sum = 0;
 
    // Loop to find  sum of changes
    for (int i = 0; i < N; i++) {
 
        // Adding difference of original
        // and required element to answer
        sum += abs(arr[i] - ele);
        ele++;
    }
    return sum;
}
 
// Driver code
int main()
{
    int N = 5;
    int arr[] = { 13, 6, 11, 18, 4 };
 
    cout << minChanges(arr, N);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
 
  // Function to output sum of all the
  // required changes in array
  static int minChanges(int arr[], int N)
  {
    Arrays.sort(arr);
 
    // Stores median of array
    int mid = arr[N / 2];
 
    // Variable for position of median
    int pos = N / 2;
 
    // Smallest element of
    // the required array
    int ele = mid - pos;
    int sum = 0;
 
    // Loop to find  sum of changes
    for (int i = 0; i < N; i++)
    {
 
      // Adding difference of original
      // and required element to answer
      sum += Math.abs(arr[i] - ele);
      ele++;
    }
    return sum;
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    int N = 5;
    int arr[] = { 13, 6, 11, 18, 4 };
    int ans = minChanges(arr, N);
    System.out.println(ans);
  }
}
 
// This code is contributed by hrithikgarg03188

# Python code for the above approach
import math as Math 
 
# Function to output sum of all the
# required changes in array
def minChanges(arr, N):
    arr.sort();
 
    # Stores median of array
    mid = arr[N // 2];
 
    # Variable for position of median
    pos = N // 2;
 
    # Smallest element of
    # the required array
    ele = mid - pos;
    sum = 0;
 
    # Loop to find  sum of changes
    for i in range(N):
 
        # Adding difference of original
        # and required element to answer
        sum += Math.fabs(arr[i] - ele);
        ele += 1
    return int(sum);
 
# Driver code
N = 5;
arr = [13, 6, 11, 18, 4];
print(minChanges(arr, N));
 
# This code is contributed by Saurabh Jaiswal

// C# program for above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
   
  // Function to output sum of all the
  // required changes in array
  static int minChanges(int[ ] arr, int N)
  {
    Array.Sort(arr);
 
    // Stores median of array
    int mid = arr[N / 2];
 
    // Variable for position of median
    int pos = N / 2;
 
    // Smallest element of
    // the required array
    int ele = mid - pos;
    int sum = 0;
 
    // Loop to find  sum of changes
    for (int i = 0; i < N; i++)
    {
       
      // Adding difference of original
      // and required element to answer
      sum += Math.Abs(arr[i] - ele);
      ele++;
    }
    return sum;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int N = 5;
    int[ ] arr = { 13, 6, 11, 18, 4 };
 
    Console.WriteLine(minChanges(arr, N));
  }
}
 
// This code is contributed by hrithikgarg03188

<script>
      // JavaScript code for the above approach
 
 
      // Function to output sum of all the
      // required changes in array
      function minChanges(arr, N) {
          arr.sort(function (a, b) { return a - b })
 
          // Stores median of array
          let mid = arr[Math.floor(N / 2)];
 
          // Variable for position of median
          let pos = Math.floor(N / 2);
 
          // Smallest element of
          // the required array
          let ele = mid - pos;
          let sum = 0;
 
          // Loop to find  sum of changes
          for (let i = 0; i < N; i++) {
 
              // Adding difference of original
              // and required element to answer
              sum += Math.abs(arr[i] - ele);
              ele++;
          }
          return sum;
      }
 
      // Driver code
 
      let N = 5;
      let arr = [13, 6, 11, 18, 4];
 
      document.write(minChanges(arr, N));
 
// This code is contributed by Potta Lokesh
  </script>

15

Complejidad de tiempo : O(N * logN)
Espacio auxiliar : O(1)