Last Updated: 29 Dec, 2020
Count Squares
Moderate
Asked in companies
You are given a matrix of size N * M. Can you count the number of squares in it?
As the count will be very large, so compute it with modulo 10^9 + 7.
For Example:
Let N = 3 and M = 5
The number of squares of size 1 will be 15.
The number of squares of size 2 will be 8.
The number of squares of size 3 will be 3.
Thus the answer will be 26.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first and only line of each test case contains two space seperated integers N and M denoting the dimensions of the matrix.
Output format :
For each test case, return an integer denoting the count of squares in the matrix modulo 10^9 + 7.
Note:
Don’t print anything, just return the count of squares in the matrix modulo 10^9 + 7.
Constraints:
1 <= T <= 10^5
1 <= N <= 10^9
1 <= M <= 10^9
Time limit: 1 sec
Approaches
The brute force approach is to count the number of squares of each size
- The number of squares of size i will be (N - i + 1) * (M - i + 1) if the square of size i fits in the matrix.
- Now we need to find ∑ (N - i + 1) * (M - i + 1) over each possible value of i.
A better approach would be generating a formula to count the number of squares.
The number of squares in a matrix of size N * N will be ∑ (N - i)^2 or ∑ i^2 which is equal to (N (N+1) (2N + 1)) / 6.
Now if we try to insert a column the matrix will be of size N * (N + 1). Now let’s count how many new squares are possible.
- The number of squares of size 1 will be N.
- The number of squares of size 2 will be N - 1.
- The number of squares of size 3 will be N - 2.
- And so on..
So the number of new squares will be ∑ (N - i) or ∑ i which is equal to (N (N+1))/2.
Now, we need to add M - N new columns to get the matrix of size N * M.
Thus, total no of squares will be:
(N (N+1) (2N + 1)) / 6 + (N (M-N) (N + 1)) / 2
Solving further we get:
(N (N+1) (3M-N+1)) / 6
Note: Here we assumed that M is greater than N. If M is smaller than N, then swap N and M.