Count Squares

Moderate

0/80

Average time to solve is 25m

22 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
3 5
2 3

Sample Output 1:

26
8

Explanation

Test Case 1: Refer to the example described above.

Test Case 2:
The number of squares of size 1 will be 6.
The number of squares of size 2 will be 2.
Thus, the answer will be 8.

Sample Input 2:

Sample Output 2:

8
50
14

Hint 1

Hint 2

The brute force approach is to count the number of squares of each size

Approaches (2)

Approach 1

Approach 2

Loop Calculation

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.

Time Complexity

O(min(N, M)) per test case where N and M are the dimensions of the matrix.

In the worst case, we will be running a loop min(N, M) times.

Space Complexity

O(1) per test case.

In the worst case, we are using constant extra space.

(100% EXP penalty)

Count Squares

Console