Encuentre el número de cuadrados dentro de la cuadrícula dada

Dada una cuadrícula de lado N * N , la tarea es encontrar el número total de cuadrados que existen dentro de ella. Todos los cuadrados seleccionados pueden tener cualquier longitud.
Ejemplos: 
 

Entrada: N = 1 
Salida: 1 
 

Entrada: N = 2 
Salida: 5 
 

Entrada: N = 4 
Salida: 30 
 

Enfoque 1: tomando algunos ejemplos, se puede observar que para una cuadrícula de tamaño N * N , el número de cuadrados dentro de ella será 1 ² + 2 ² + 3 ² + … + N ²
A continuación se muestra la implementación de lo anterior Acercarse:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number
// of squares inside an n*n grid
int cntSquares(int n)
{
    int squares = 0;
    for (int i = 1; i <= n; i++) {
        squares += pow(i, 2);
    }
    return squares;
}
 
// Driver code
int main()
{
    int n = 4;
 
    cout << cntSquares(4);
 
    return 0;
}

// Java implementation of the approach
class GFG {
 
    // Function to return the number
    // of squares inside an n*n grid
    static int cntSquares(int n)
    {
        int squares = 0;
        for (int i = 1; i <= n; i++) {
            squares += Math.pow(i, 2);
        }
        return squares;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 4;
 
        System.out.print(cntSquares(4));
    }
}

# Python3 implementation of the approach
 
# Function to return the number
# of squares inside an n*n grid
def cntSquares(n) :
 
    squares = 0;
    for i in range(1, n + 1) :
        squares += i ** 2;
 
    return squares;
 
# Driver code
if __name__ == "__main__" :
 
    n = 4;
 
    print(cntSquares(4));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the number
    // of squares inside an n*n grid
    static int cntSquares(int n)
    {
        int squares = 0;
        for (int i = 1; i <= n; i++)
        {
            squares += (int)Math.Pow(i, 2);
        }
        return squares;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int n = 4;
 
        Console.Write(cntSquares(n));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
    // JavaScript implementation of the approach
     
    // Function to return the number
    // of squares inside an n*n grid
    function cntSquares(n)
    {
        let squares = 0;
        for (let i = 1; i <= n; i++)
        {
            squares += Math.pow(i, 2);
        }
        return squares;
    }
     
    let n = 4;
   
      document.write(cntSquares(n));
             
</script>

30

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Enfoque 2: Mediante el uso de fórmula directa. 
Sin embargo, la suma  tiene la forma cerrada (fórmula directa)  . Por lo tanto, podemos emplear esto para calcular la suma en el  tiempo.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <iostream>
 
using namespace std;
 
int cnt_squares (int n)
{
    /* Function to return the number
     of squares inside an n*n grid */
 
    return n * (n + 1) * (2 * n + 1) / 6;
}
 
// Driver code
int main()
{
    cout << cnt_squares (4) << endl;
 
    return 0;
}

// Java implementation of the approach
class GFG {
    static int cntSquares (int n) {
        /* Function to return the number
        of squares inside an n*n grid */
     
        return n * (n + 1) * (2 * n + 1) / 6;
    }
 
    // Driver code
    public static void main(String args[]) {
        System.out.println (cntSquares(4));
    }
}

# Python3 implementation of the approach
 
"""
Function to return the number
of squares inside an n*n grid
"""
 
def cntSquares(n) :
    return int (n * (n + 1) * (2 * n + 1) / 6)
 
# Driver code
if __name__ == "__main__" :
    print (cntSquares (4));

// C# implementation of the approach
using System;
 
class GFG
{
 
    /* Function to return the number
     of squares inside an n*n grid */
    static int cntSquares (int n)
    {
        return n * (n + 1) * (2 * n + 1) / 6;
    }
 
    // Driver code
    public static void Main (String[] args)
    {
        Console.Write (cntSquares (4));
    }
}

<script>
    // Javascript implementation of the approach
     
    /* Function to return the number
     of squares inside an n*n grid */
    function cntSquares (n)
    {
        return n * (n + 1) * (2 * n + 1) / 6;
    }
     
    document.write(cntSquares(4));
 
// This code is contributed by divyeshrabadiya07.
</script>

30

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)