JavaScript program to find Number of Squares in an N*N grid

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)