Last Updated: 11 Dec, 2020
Count Of Divisible Pairs
Easy
You are given two integers ‘N’ and ‘M’. A pair (x, y) is a divisible pair if it satisfies the following conditions:
a) 1 <= x <= ‘N’
b) 1 <= y <= ‘M’
c) x + y is divisible by 5.
Your task is to return the count of all divisible pairs that can be formed from given ‘N’ and ‘M’.
Example :
If N = 3 and M = 5, then { x = 1, y = 4 }, { x = 2, y = 3 }, { x = 3, y = 2 } are the pairs that satisfy the given conditions.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows
The first line of each testcase contains two integers ‘N’ and ‘M’.
Output Format :
For each test case print a single integer denoting the count of divisible pairs.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N, M <= 10^9
Time limit: 1 sec
Approaches
We can create all pairs possible and check the condition of divisibility.
To create all the pairs, for each x in the range [1, N] iterate through all y in the range [1, M].
The steps are as follows :
- Initialize count to 0.
- Run outer for loop for x from 1 to N
- Run inner for loop for y from 1 to M
- For each generated pair of (x,y) increment the count if the x+y is divisible by 5.
- Return the final value of count.
We know ( x + y ) % 5 = ( (x%5) + (y%5) ) % 5.
Using this we can easily notice sum of x and y can only be divisible by 5 when:
- x % 5 = 0 and y % 5 = 0
- x % 5 = 1 and y % 5 = 4
- x % 5 = 2 and y % 5 = 3
- x % 5 = 3 and y % 5 = 2
- x % 5 = 4 and y % 5 = 1
Now simply we can count these values, multiply them and add them.
The steps are as follows:
- Create an array X, and let Xi store the count of x % 5 = i.
- Create an array Y, and let Yi store the count of y % 5 = I.
- Return the value of X0*Y0 + X1*Y4 + X2*Y3 + X3*Y2 + X4*Y1