Question
Count Squares in Grid
Given a grid of size n × n, count the total number of squares that can be formed in the grid.
1. A 1×1 square is a single cell.
2. A 2×2 square is formed by combining 4 cells , and so on, up to n×n.
1. A 1×1 square is a single cell.
2. A 2×2 square is formed by combining 4 cells , and so on, up to n×n.
Input
A single integer n (size of the grid).
Output
Count all squares of size 1×1 up to n×n that can be formed in an n×n grid, and print the total number of such squares.
Note : A k×k square is formed by selecting k consecutive rows and k consecutive columns.
Note : A k×k square is formed by selecting k consecutive rows and k consecutive columns.
Example
Example 1:
Input:
3
Output:
14
Example 2:
Input:
4
Output:
30
Explanation:
1. For n = 3:
1×1 squares = 9
2×2 squares = 4
3×3 squares = 1
Total = 9 + 4 + 1 = 14
2. For n = 4:
1×1 = 16, 2×2 = 9, 3×3 = 4, 4×4 = 1
Total = 16 + 9 + 4 + 1 = 30
Input:
3
Output:
14
Example 2:
Input:
4
Output:
30
Explanation:
1. For n = 3:
1×1 squares = 9
2×2 squares = 4
3×3 squares = 1
Total = 9 + 4 + 1 = 14
2. For n = 4:
1×1 = 16, 2×2 = 9, 3×3 = 4, 4×4 = 1
Total = 16 + 9 + 4 + 1 = 30