Find Number of Squares in an N x N Grid Using JavaScript

A grid is a 2-dimensional arrangement of squares divided into rows and columns. From a given N*N square grid we have to calculate the total number of squares possible. There are multiple ways to find the number of squares in a given grid. In this article, we are going to learn about various approaches for calculating the number of squares in a given grid of size N*N.

Direct Formula for Finding the Number of Squares in an N*N Grid

The direct formula for finding the total number of squares in an N * N grid is

Total Number of Squares = (N * (N + 1) * (2N + 1)) / 6

Example 1

Input: 4
Output: 30

Explanation

Total squares in a 4 * 4 grid are

1x1 squares = 16 Squares
2x2 squares = 9 Squares
3x3 squares = 4 Squares
4x4 squares = 1 Squares
Total Number of Squares = 16 + 9 + 4 + 1 = 30

Example 2

Input: 3
Output: 14

Explanation

Total squares in a 3 * 3 grid are

1x1 squares = 9 Squares
2x2 squares = 4 Squares
3x3 squares = 1 Squares

Total Number of Squares = 9 + 4 + 1 = 14

Different Approaches to Find the Number of Squares in an N * N Grid

Using the Direct Formula Approach

This is the most simple, direct, and efficient approach for finding the number of squares in an N * N grid. We can use the above-discussed mathematical formula directly to get the answer.

Steps for Implementation

• First, take the input value N.
• Now, calculate the total squares using the formula (N * (N + 1) * (2N + 1)) / 6.
• Output the answer.

Implementation Code

// Define the grid size
let gridSize = 4;

// Calculate the total squares using the formula
let totalSquares = (gridSize * (gridSize + 1) * (2 * gridSize + 1)) / 6;

// Output the result
console.log(`The total number of squares in a ${gridSize}x${gridSize} grid is ${totalSquares}`);

Output

The total number of squares in a 4x4 grid is 30

Time Complexity

O(1)

Space Complexity

O(1)

Using a Loop

In this approach, we iterate through all possible square sizes and add up the number of squares for each size to the final answer.

Steps for Implementation

• First, take the input value of N.
• No, Initialize a variable to store the total count.
• Loop from size 1 to N and add the squares.
• Output the answer.

Implementation Code

// Define the grid size
let gridSize = 3;

// Initialize result variable
let totalSquares = 0;

// Loop through all possible square sizes
for (let size = 1; size <= gridSize; size++) {
    totalSquares += (gridSize - size + 1) * (gridSize - size + 1);
}

// Output the result
console.log(`The total number of squares in a ${gridSize}x${gridSize} grid is ${totalSquares}`);

Output

The total number of squares in a 3x3 grid is 14

Time Complexity

O(N)

Space Complexity

O(1)

Using Recursion

In this approach, we use a recursive function to find the total number of squares.
The recursive approach reduces the size of the problem.

Steps for Implementation

• Define a recursive function that calculates squares for a given number N.
• Base case If N = 1, return 1.
• Recursive case For recursive cases add N * N to the recursive call with N - 1.
• Output the answer.

Implementation Code

// Recursive function to calculate total squares
function countSquares(n) {
    if (n === 1) return 1;
    return (n * n) + countSquares(n - 1);
}

// Define the grid size
let gridSize = 3;

// Calculate total squares using recursion
let totalSquares = countSquares(gridSize);

// Output the result
console.log(`The total number of squares in a ${gridSize}x${gridSize} grid is ${totalSquares}`);

Output

The total number of squares in a 3x3 grid is 14

Time Complexity

O(N)

Space Complexity

O(N) (due to recursive stack calls)