Movimientos mínimos necesarios para mover monedas de cada celda a cualquier celda de Matrix

Dado un número impar N que representa una cuadrícula de tamaño N x N que inicialmente está llena de monedas, la tarea es encontrar el número mínimo de movimientos necesarios para que todas las monedas se muevan a cualquier celda de la cuadrícula de modo que en cada paso, alguna moneda arbitraria en el medio de la cuadrícula puede moverse a cualquiera de las ocho celdas circundantes. 

Ejemplos: 

Entrada: N = 3 
Salida: 8 
Explicación: 
Hay un total de 9 celdas en una cuadrícula de 3 x 3. Suponiendo que hay que llevar todas las monedas a la celda central, se deben mover 8 monedas y el número de pasos es 8. 

Entrada: N = 5 
Salida: 40 
 

Aproximación: el número mínimo de pasos se obtiene solo cuando todas las monedas se mueven al centro de la cuadrícula. Por lo tanto, la idea es dividir toda la grilla en múltiples capas.  

• Cada capa de la cuadrícula K necesita K movimientos para llegar al centro. Eso es: 
  1. Las monedas en la capa 1 dan un paso para moverse hacia el centro.
  2. Las monedas en la capa 2 dan dos pasos para moverse hacia el centro y así sucesivamente.
• Por ejemplo, sea N = 5. Luego, la cuadrícula se divide en las capas de la siguiente manera:
• En la ilustración anterior, las monedas que están marcadas en rojo están en la capa 1 y las monedas que están marcadas en azul están en la capa 2.
• De manera similar, para una cuadrícula de tamaño N x N, podemos dividir las monedas en N//2 capas.
• En cada capa K, el número de monedas presentes es (8 * K). Y, la cantidad de pasos requeridos es K. Por lo tanto, itere a través de todas las capas y encuentre la cantidad total de pasos como 8 * K ²

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

// C++ program to find the minimum number
// of moves taken to move the element of
// each cell to any one cell of the
// square matrix of odd length
#include <iostream>
using namespace std;
 
// Function to find the minimum number
// of moves taken to move the element 
// of each cell to any one cell of the
// square matrix of odd length
int calculateMoves(int n)
{
     
    // Initializing count to 0
    int count = 0;
 
    // Number of layers that are
    // around the centre element
    int layers = n / 2;
 
    // Iterating over ranger of layers
    for(int k = 1; k < layers + 1; k++)
    {
 
       // Increase the value of count 
       // by 8 * k * k
       count += 8 * k * k;
    }
    return count;
}
 
// Driver code
int main()
{
    int N = 5;
     
    cout << calculateMoves(N);
}
 
// This code is contributed by coder001

// Java program to find the minimum number
// of moves taken to move the element of
// each cell to any one cell of the
// square matrix of odd length
class GFG{
     
// Function to find the minimum number
// of moves taken to move the element
// of each cell to any one cell of the
// square matrix of odd length
public static int calculateMoves(int n)
{
         
    // Initializing count to 0
    int count = 0;
     
    // Number of layers that are
    // around the centre element
    int layers = n / 2;
     
    // Iterating over ranger of layers
    for(int k = 1; k < layers + 1; k++)
    {
         
       // Increase the value of count
       // by 8 * k * k
       count += 8 * k * k;
    }
    return count;
}
 
// Driver code   
public static void main(String[] args)
{
    int N = 5;
     
    System.out.println(calculateMoves(N));
}
}
 
// This code is contributed by divyeshrabadiya07   

# Python3 program to find the minimum number
# of moves taken to move the element of
# each cell to any one cell of the
# square matrix of odd length
 
# Function to find the minimum number
# of moves taken to move the element of
# each cell to any one cell of the
# square matrix of odd length
def calculateMoves(n):
 
    # Initializing count to 0
    count = 0
 
    # Number of layers that are
    # around the centre element
    layers = n//2
 
    # Iterating over ranger of layers
    for k in range(1, layers + 1):
 
        # Increase the value of count by
        # 8 * k * k
        count+= 8 * k*k
 
    return count
 
# Driver code
if __name__ == "__main__":
 
    N = 5
  
    print(calculateMoves(N))

// C# program to find the minimum number
// of moves taken to move the element of
// each cell to any one cell of the
// square matrix of odd length
using System;
class GFG{
     
// Function to find the minimum number
// of moves taken to move the element
// of each cell to any one cell of the
// square matrix of odd length
public static int calculateMoves(int n)
{
         
    // Initializing count to 0
    int count = 0;
     
    // Number of layers that are
    // around the centre element
    int layers = n / 2;
     
    // Iterating over ranger of layers
    for(int k = 1; k < layers + 1; k++)
    {
         
        // Increase the value of count
        // by 8 * k * k
        count += 8 * k * k;
    }
    return count;
}
 
// Driver code
public static void Main()
{
    int N = 5;
     
    Console.Write(calculateMoves(N));
}
}
 
// This code is contributed by Code_Mech

<script>
 
// Javascript program to find the minimum number
// of moves taken to move the element of
// each cell to any one cell of the
// square matrix of odd length
 
// Function to find the minimum number
// of moves taken to move the element
// of each cell to any one cell of the
// square matrix of odd length
function calculateMoves(n)
{
     
    // Initializing count to 0
    var count = 0;
 
    // Number of layers that are
    // around the centre element
    var layers = parseInt(n / 2);
 
    // Iterating over ranger of layers
    for(var k = 1; k < layers + 1; k++)
    {
         
        // Increase the value of count
        // by 8 * k * k
        count += 8 * k * k;
    }
    return count;
}
 
// Driver code
var N = 5;
 
document.write(calculateMoves(N));
 
// This code is contributed by noob2000
 
</script>

40

Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(N) tiempo 
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.