PROBLEM LINK:
Author: Prakhar Gupta
Tester: Madhav Sainanee
Editorialist: Prakhar Gupta
DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
Given an N \times N chessboard, find out the number of squares with odd length.
QUICK EXPLANATION
The answer is \displaystyle\sum_{i = 0}^{\lfloor\frac{N}{2}\rfloor} {(N-2i)^2}
EXPLANATION:
For an example, let us take a chessboard of size 8 \times 8.
We take a horizontal rod of size 5 and try to slide it through the chessboard from left to right.
It can take the column numbers 1 \text{ to } 5, 2 \text{ to } 6, 3 \text{ to } 7 and 4 \text{ to } 8.
For a horizontal rod of size 4, it can take the columns 1 \text{ to } 4, 2 \text{ to } 5, 3 \text{ to } 6, 4 \text{ to } 7 and 5 \text{ to } 8.
From the above examples, we can infer that we can fit N - i + 1 rods of length i in an N \times N chessboard horizontally. Similarly, we can fit the same number of rods in the chessboard vertically, since it is a square and is symmetric.
If we consider these rods as the sides of the square of side i, we have N - i + 1 horizontal and vertical choices each. So, the number of squares of length i in a N \times N chessboard is (N - i + 1)^2.
Using this formula, we can replace i = 1, 3, 5…. as the side length of the square and add them up. This gives us \displaystyle\sum_{i = 0}^{\lfloor\frac{N}{2}\rfloor} {(N-2i)^2}.
Complexity: The time complexity is O(N) per test case.
BONUS: Try to solve the question in O(1) per test case.
Click to view
When N is even, the answer is 2^2 + 4^2 + 6^2 + ... + N^2. This can be written as 4 \times (1^2 + 2^2 + ... + \left(\frac{N}{2}\right)^2). This can easily be calculated using sum of squares.
When N is odd, the answer is 1^2 + 3^2 + ... + N^2. This can we written as (1^2 + 2^2 + 3^2 + ... + N^2) - (2^2 + 4^2 + ... + (N-1)^2) \text{ }. The first part can be solved using the sum of squares formula, and the second part can be solves as in the case of even N.
AUTHOR’S SOLUTIONS:
O(N) solution can be found here.
O(1) solution can be found here.